Concatenated Words

Hard
0/120
profile
Contributed by
2 upvotes
Asked in companies
IntuitIntuitQualcomm

Problem statement

Ninja has given a list of unique words 'WORDS' of size 'N' and he wants to find all the words in the list formed after concatenating two or more words in the same list.

As Ninja's best friend, he asked you to help him with the above problem. So, your task is to find all words in the list which are formed after concatenating two or more words in the same list.

Note: One word can be concatenated multiple times. It is guaranteed that there is at least one word in the list, which is formed after concatenating two or more words.

Example: 
Input: 'WORDS' = ["ninjas", "coding", "codingninjas"]
Output: ["codingninjas"]

Only word "codingninjas' is formed after concatenating two or more words in the list i.e "coding" and "ninjas".
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line of input contains an integer 'T', denoting the number of test cases. 

The first line contains an integer 'N' size of the list 'WORDS' for each test case. The next line contains 'N' words
Output format : 
For each test case, print all the formed words after concatenating two or more words in the input list.

Output for each test case will be printed in a separate line.
Note : 
You don't need to print anything. It has already been taken care of. Just implement the given function.
Constraints : 
1 <= ‘T’ <= 10
2 <= 'N' <= 10^2
1 <= 'WORDS[i].LENGTH'<= 10^2
Time Limit: 1 sec
Sample Input 1 :
2
3
ninjas coding codingninjas
4
cat dog catdog catdogcat
Sample Output 1 :
codingninjas
catdog catdogcat
Explanation Of Sample Input 1 :
For the first test case, the Only word "codingninjas' is formed after concatenating two or more words in the list, i.e., "coding" and "ninjas".

For the second test case, the words "catdog" and "catdogcat" concatenate two or more words in the list.
Sample Input 2 :
2
4
line input inputline inputlineline
3
solution problem problemsolution
Sample Output 2 :
inputline inputlineline
problemsolution
Hint

Can you try to match all possible combinations recursively?

Approaches (3)
Recursive Brute Force

Approach:  In this approach, for every string, we will try to match strings in the 'words' with it. We will sort out the array of strings with the size of the string, and then for every string will try to divide it into the possible substrings such that every substring contains a string in a 'words'. We will do this recursively by checking for every possible combination.

 

Algorithm : 

 

  1. Initialize the vector of string 'answer'.
  2. Sort the vector 'words' with the custom comparator 'compare'.
  3. Initialise a map of <string, int> 'visited'.
  4. Declare a 'get' function.
  5. Run a loop from 0 to 'N - 1' with variable 'i'.
    • If 'get(0, word[i], visited)' is true then push 'word[i]' in the 'answer'.
    • Updated 'visited[word[i]' by 1.
  6. Return 'answer'.

 

‘Compare’ function compares the vectors ‘a’ and ‘b’.

 

compare(a, b):

  1. Return a.size() < b.size()

 

‘get’ function will return true if current word is formed after concatenating some strings in input array or not else it will return false.

 

get(index, word, visited):

  1. If 'index == word.size()' then return true.
  2. If 'visited.count(word)' is true then return true.
  3. Initialize a variable 'flag' by false.
  4. Initialize a string 'current'.
  5. Run a loop from 'index' to 'word.size()' with variable 'i'.
    • Push 'word[i]' in the 'current'.
    • If 'visited.count(current)' and 'get(i + 1, word, visited)' are both true then update 'flag' with true and break out of the loop.
  6. Return 'flag'.
Time Complexity

O(M * N!), Where 'N' is the size of the input vector 'words' and 'M' is the max size of 'words[i]'.

 

As we are recursively checking for all possible permutations and, there can be N! permutations in the worst case. And for each permutation we are iterating over, it will consume another linear time. hence the time complexity will be O(M * M!).

Space Complexity

O(M * N), Where 'N' is the size of the input vector 'words' and 'M' is the max size of 'words[i]'.
 

As we are using extra 'visited' and 'answer' arrays of max size 'N' and with max size of the word in it 'M', the space complexity will be O(N * M).

Code Solution
(100% EXP penalty)
Concatenated Words
Full screen
Console