New update is available. Click here to update.

Word Break

PROBLEM STATEMENT

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

Approach 1

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.

Try Problem

Approach 2

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.

Try Problem

Approach 3

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.

Try Problem

Approach 4

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.

Try Problem

Word Break

PROBLEM STATEMENT

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 :

Examples :

Input format :

Output format :

Note:

Constraints :

Approach 1

Approach 2

Approach 3

Approach 4

Interested in Coding Ninjas Flagship Courses?