 New update is available. Click here to update.

# Word Break

Last Updated: 15 Jan, 2021
Difficulty: Moderate

## 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:

1. Store all strings of A on the hash map.
2. Declare and call function wordBreakHelper which will take a single argument string.

wordBreakHelper(s):

1. Base case if the length of the string is 0 then return true.
2. 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.
3. After running the loop, return false.