Posted: 15 Jan, 2021
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.
You can use any string of A multiple times.
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.
You do not need to print anything, it has already been taken care of. Just implement the given function.
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.
- Store all strings of A on the hash map.
- Declare and call function wordBreakHelper which will take a single argument string.
- 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.