Concatenated Words

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'.

Approach: We optimize it more by storing some immediate results in the above approach. For each word, we can store to what extent we are able to make the substrings of it, so all of them are from the given word list only. We will use the intermediate stored results to find the answer for the next stages.

 

By storing the above data in the 'wordDp' map, we will decrease the time complexity from factorial to the polynomial.

 

Algorithm : 

1. Initialize the vector of string 'answer'.
2. sort the vector 'words' with the custom comparator 'compare'.
3. Initialise a unordered map of <string, int> 'visited'.
4. Initialise a unordered map 'wordDp' of <int, unordered_map<int, int>.
5. Declare a 'get' function.
6. Run a loop from 0 to 'N - 1' with variable 'i'.
   • If 'get(0, i, word[i], 'wordDp', visited)' is true then push 'word[i]' in the 'answer'.
   • Updated 'visited[word[i]]' by 1.
7. 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 concatening some strings in input array or not else it will return false.

get(index, wordIndex, word, wordDp, visited):

1. If 'index == word.size()' then return “true”.
2. If 'visited.count(word)' is true then return “true”.
3. If 'wordDp[wordIndex].count(index)' is true then return 'wordDp[wordIndex].count(index)'.
4. Initialize a variable 'flag' by “false”.
5. Initialize a string 'current'.
6. 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, wordIndex, word, wordDp, visited)' are both true then update 'flag' with true and break out of the loop.
7. Update 'wordDp[wordIndex][index]' with 'flag'.
8. Return 'flag'.

Approach: We will implement the same above logic iteratively in this approach. The main observation is that for any word formed after concatenation, there must be at least three indexes (at least one besides 0 and n-1, which n is the length of the word), which can be used to split the whole string into at least two substrings and all substrings can be found in words.

We will iterate over all the words and, for each word, will keep track of the till what index we can form the substrings using the 'DP' array.

Algorithm : 
 

1. Initialize the vector of string 'answer'.
2. Initialize the unordered map of <string, bool> 'isPresent'.
3. Iterate over the vector 'words' using iterator string 'word' and update the value for each word in 'isPresent' by “true”.
4. Iterate over the vector 'words' using iterator string 'word'.
   • Initialize the variable 'M' and update it by 'word.size()'.
   • Initialize the vector 'DP' of size 'M + 1'.
   • Update 'DP[M]' by 1.
   • Run a loop from 'M - 1' to 0 with variable 'J'
     • Initialize the empty string 'current'.
     • Initialize the variable 'K' by 'J'.
     • Run a while loop till 'K' < 'M'.
       • Update 'current' by 'current + word[k]'.
       • If 'DP[K + 1]' > 0 && 'isPresent[current]' then update 'DP[J]' by 'DP[J] + DP[K + 1] + 1' and break out of the loop.
       • Increment 'K' by 1.
   • If 'DP[0]' > 0 then push 'word' in 'answer'.
5. Return 'answer'.