Last Updated: 15 Jan, 2021
Word Break
Moderate
Asked in companies
You are given a list of “N” strings A. Your task is to check whether you can form a given target string using a combination of one or more strings of A.
Note :
You can use any string of A multiple times.
Examples :
A =[“coding”, ”ninjas”, “is”, “awesome”] target = “codingninjas”
Ans = true as we use “coding” and “ninjas” to form “codingninjas”
Input format :
The first line of input contains a single integer T, representing the number of test cases or queries to be run.
Then the T test cases follow.
The first line of each test contains a single integer N denoting the total number of strings in A.
The second line of each test contains “N” space-separated strings of A.
The third line of each test contains a single string target.
Output format :
For each test case, print 1 if you can form a target string else print 0.
The output of each test case will be printed in a separate line.
Note:
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints :
1 <= T <= 5
1 <= N, | target | <= 10^2
1 <= | A[i] | <= 10
Where | A[i] | denotes length of string i,| target | denotes the length of the string target and A[i] contains only lowercase English characters.
Time limit: 1 sec
Approaches
In this solution, we will try to generate all prefixes and If we want a prefix present in the string then we will recur for the remaining string.
Steps:
- Store all strings of A on the hash map.
- Declare and call function wordBreakHelper which will take a single argument string.
wordBreakHelper(s):
- Base case if the length of the string is 0 then return true.
- Run a loop from i = 1 to the length of the string:
- If substring from 0 to i exist in the map and recursion of the remaining string gives true then return true.
- After running the loop, return false.
In this solution, we will use the Overlapping Subproblems property. We will store the already calculated result in a dp array.
Here we will store the result of our recursion in a dp array.
We can implement the above approach by –
- Store all strings of A on the hash map.
- Declare a function wordBreakHelper which will take three arguments: string, start, and dp array.
- If start equals the length of the string then return true.
- Run a loop from i = 1 to the length of the string.
- If dp[start] is already calculated then return it.
- If substring from 0 to i exists in the map and recursion of the remaining string gives true then return true.
- After running the loop, return false.
In this solution, we will Bottom Up dp.
Here first we will store all strings of A in a hashmap. Then we will declare a dp array and run two loops and mark dp[i] true if and only if there exists a j such that substring from index j to index i is present in hashmap and dp[j] is already true.
Steps :
- Store all strings of A in a hashmap.
- Declare a dp array of size equal to the length of the target string and mark all its elements with false.
- Initialize dp[0] as true.
- Run a loop from i = 1 to the length of the target string.
- Run a loop from j = i - 1 to zero.
- If dp[j] is true and substring from j to i is present in hashmap then mark dp[i] as true and break the loop
- Return dp[n] where n is the length of the target string.
In this solution, we will use a graph to represent all possible solutions. The vertices are the position of first character of a word and edges will represent the whole word.
We will use a hashmap to keep track of visited nodes.
Steps :
- Store all elements of A in a hashmap.
- Declare an empty queue q and hashmap visited.
- Push 0 to q.
- Run a loop until the queue is not empty.
- Pop the top element of the queue.
- If the top element is not visited then mark it as visited.
- Then run a loop from j = top element till the length of the target string
- If the suffix of the string starting from j not exist in the hashmap then push j to q.
- If j = length of target string then returns true.
- If no solution exists then return false.