# Word Break

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

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.