Word Break

Posted: 15 Jan, 2021
Difficulty: Moderate

PROBLEM STATEMENT

Try Problem

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.
Try Problem