Array     C++     Depth-First Search     Dynamic Programming     Hard     String     Trie    

Problem Statement:

Given an array of strings words (without duplicates), return all the concatenated words in the given list of words.

A concatenated word is defined as a string that is comprised entirely of at least two shorter words (not necesssarily distinct) in the given array.

 

Example 1:

Input: words = ["cat","cats","catsdogcats","dog","dogcatsdog","hippopotamuses","rat","ratcatdogcat"]
Output: ["catsdogcats","dogcatsdog","ratcatdogcat"]
Explanation: "catsdogcats" can be concatenated by "cats", "dog" and "cats"; 
"dogcatsdog" can be concatenated by "dog", "cats" and "dog"; 
"ratcatdogcat" can be concatenated by "rat", "cat", "dog" and "cat".

Example 2:

Input: words = ["cat","dog","catdog"]
Output: ["catdog"]

 

Constraints:

  • 1 <= words.length <= 104
  • 1 <= words[i].length <= 30
  • words[i] consists of only lowercase English letters.
  • All the strings of words are unique.
  • 1 <= sum(words[i].length) <= 105

Solution:

Intuition

Intuition is from Word Break. Basically we check at each position, if there is a valid word from any previous position. Reproducing my solution for Word Break below:

 
bool wordBreak(string s, vector<string>& words) 
{
    unordered_set<string> wordSet(words.begin(),words.end());
    int n = s.length();
    vector<bool> valid(n+1, false);
    valid[0] = true;
    for (int j=1; j<=n; j++)
        for (int i=0; i<j && !valid[j]; i++)
            valid[j] = valid[i] && wordSet.count(s.substr(i,j-i));
    return valid[n];
}

Approach

We just repeat Word Break for each word with all the other words.

Complexity

  • Time complexity: $O(NM^3)$ where N is size of words array and M is the length of longest word. $NM^2$ can be seen clearly from the for loops in code below. Extra M term is for string hashing.

  • Space complexity: $O(N*M)$

Code

 
class Solution {
public:
    vector<string> findAllConcatenatedWordsInADict(vector<string>& words) 
    {
        unordered_set<string> wordSet(words.begin(),words.end());
        vector<string> res;
        for (string word: words)
        {
            wordSet.erase(word);
            int n = word.length();
            vector<bool> valid(n+1, false);
            valid[0] = true;
            for (int j=1; j<=n; j++)
                for (int i=0; i<j && !valid[j]; i++)
                    valid[j] = valid[i] && wordSet.count(word.substr(i,j-i));
            if (valid[n]) res.push_back(word);
            wordSet.insert(word);
        }
        return res;        
    }
};