Problem

Submissions

Hints & solutions

Discuss

Word Break

Moderate

0/80

Average time to solve is 15m

Contributed by

39 upvotes

Asked in companies

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”

Detailed explanation ( Input/output format, Notes, Images )

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

Sample Input 1 :

2 
2
ab cd
abcd
2
do the
hello

Sample Output 1 :

1
0

Explanation For Sample Input 1:

For the first test case, A = [ “ab”, “cd”], target = “abcd”
We can get “abcd” using “ab” and “cd”
So answer will be 1.

For the second test case, A = [ “do”, “the”], target = “hello”
We can’t make a target using one or more strings of A.
So the answer will be 0.

Sample Input 2 :

2 
2
aa a
aaaaa
1
do
d

Sample Output 2 :

1
0

Explanation For Sample Input 2:

For the first test case, A =[ “aa”, “a”], target = “aaaaa”
We can use “a” 5 times to get “aaaaa”.
So the answer will be 1.

For the second test case, A =[ “do”], target = “d”
We can’t make d using [“do”].
So the answer will be 0.

Hint 1

Hint 2

Hint 3

Hint 4

Think of a solution using brute force.

Approaches (4)

Approach 1

Approach 2

Approach 3

Approach 4

Brute Force

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.

Time Complexity

O(2^N), where N is the length of the target string.

In the worst case, we are generating all combinations which will take O(2^N) time. Hence the overall complexity will be O(2^N ).

Space Complexity

O(N).

We are using a hash map which will require O(N) space.

(75% EXP penalty)

(100% EXP penalty)

Word Break

Console