Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/472.html

472. Concatenated Words (Hard)

Given a list of words (without duplicates), please write a program that returns all 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 in the given array.

Example:

Input: ["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".

Note:

  1. The number of elements of the given array will not exceed 10,000
  2. The length sum of elements in the given array will not exceed 600,000.
  3. All the input string will only include lower case letters.
  4. The returned elements order does not matter.

Companies:
Amazon, Apple

Related Topics:
Dynamic Programming, Depth-first Search, Trie

Similar Questions:

Solution 1. Trie + C++ Static Pool

Use Trie to store the words.

Use DFS to check whether a word is a concatenated word: traverse from the first letter in word, whenever we meet an word ending, start a new DFS call and re-search from the trie root. If the word is exhausted by matching at least two words, return true; otherwise return false.

// OJ: https://leetcode.com/problems/concatenated-words/
// Time: O(N*2^W) where N is length of words array, W is max word length. 
//       2^W is because for each letter we may start or not start a new check there.
// Space: O(C) where C is the length sum of words.
// Ref: https://discuss.leetcode.com/topic/72754/trie-dfs-method-using-static-trie-node-to-avoid-getting-mle-runtime-about-300ms
// NOTE: Use statically allocated memory to avoid MLE in C++.
class TrieNode {
public:
    bool end = false;
    TrieNode *next[26];
};

TrieNode pool[60000];

class Solution {
private:
    TrieNode *root = pool;
    int cnt = 1;
    void insert(string &word) {
        TrieNode *node = root;
        for (char c : word) {
            if (!node->next[c - 'a']) node->next[c - 'a'] = &pool[cnt++];
            node = node->next[c - 'a'];
        }
        node->end = true;
    }
    
    bool check(string &word, int start) {
        if (start == word.size()) return true;
        TrieNode *node = root;
        for (int i = start; i < word.size(); ++i) {
            node = node->next[word[i] - 'a'];
            if (!node) return false;
            if (i != word.size() - 1 && node->end && check(word, i + 1)) return true;
        }
        return node->end && start;
    }
public:
    vector<string> findAllConcatenatedWordsInADict(vector<string>& words) {
        memset(pool, 0, sizeof(pool)); // reset pool.
        for (string s : words) insert(s);
        vector<string> ans;
        for (string s : words) {
            if (s.empty()) continue;
            if (check(s, 0)) ans.push_back(s);
        }
        return ans;
    }
};

Solution 2: Trie + unordered_map

Same idea as Solution 1, instead of using statically allocated pool, use unordered_map to store children mapping in TrieNode.

// OJ: https://leetcode.com/problems/concatenated-words/
// Time: O(N*2^W) where N is length of words array, W is max word length. 
//       2^W is because for each letter we may start or not start a new check there.
// Space: O(C) where C is the length sum of words.
// NOTE: use `unordered_map` instead of `TrieNode*[26]` to save space.
class TrieNode {
public:
    unordered_map<char, TrieNode*> children;
    bool isWord = false;
};

class Trie {
private:
    TrieNode root;
    bool dfs(string &word, int start, int cnt) {
        if (start == word.size()) return cnt > 1;
        TrieNode *node = &root;
        for (int i = start; i < word.size(); ++i) {
            if (node->children.find(word[i]) == node->children.end()) return false;
            TrieNode *next = node->children[word[i]];
            if (next->isWord && dfs(word, i + 1, cnt + 1)) return true;
            node = next;
        }
        return false;
    }
public:
    void insert(string &word) {
        TrieNode *node = &root;
        for (char c : word) {
            if (!node->children[c]) {
                node->children[c] = new TrieNode();
            }
            node = node->children[c];
        }
        node->isWord = true;
    }
    
    bool isConcatednatedWord(string &word) {
        return dfs(word, 0, 0);
    }
};
class Solution {
public:
    vector<string> findAllConcatenatedWordsInADict(vector<string>& words) {
        Trie trie;
        for (auto word : words) trie.insert(word);
        vector<string> ans;
        for (auto word : words) {
            if (trie.isConcatednatedWord(word)) ans.push_back(word);
        }
        return ans;
    }
};

Solution 3. DP

Use dp[i] to denote whether word[0..i] is a concatenated word.

dp[i] = true, if there is a j[0,i] such that word[0..j] and word[j..i] are all words in words array.

In my opinion, this is just doing DFS in another way.

// OJ: https://leetcode.com/problems/concatenated-words/
// Time: O(N*W^3)
// Space: O(C) where C is the length sum of words.
// Ref: https://discuss.leetcode.com/topic/72393/c-772-ms-dp-solution
class Solution {
private:
    unordered_set<string> s;
    bool isConcatenatedWord(string &word) {
        int W = word.size();
        vector<bool> dp(W, false);
        for (int i = 0; i < W - 1; ++i) {
            if (s.count(word.substr(0, i + 1))) dp[i] = true;
            if (!dp[i]) continue;
            for (int j = i + 1; j < W; ++j) {
                if (s.count(word.substr(i + 1, j - i))) dp[j] = true;
            }
            if (dp[W - 1]) return true;
        }
        return false;
    }
public:
    vector<string> findAllConcatenatedWordsInADict(vector<string>& words) {
        s = unordered_set<string>(words.begin(), words.end());
        vector<string> ans;
        for (string &word : words) {
            if (isConcatenatedWord(word)) ans.push_back(word);
        }
        return ans;
    }
};
  • class Solution {
        TrieNode root = new TrieNode();
    
        public List<String> findAllConcatenatedWordsInADict(String[] words) {
            List<String> concatenateWords = new ArrayList<String>();
            if (words == null || words.length == 0)
                return concatenateWords;
            for (String word : words) {
                if (word.length() > 0)
                    insert(word);
            }
            for (String word: words) {
                if (depthFirstSearch(word, root, 0, 0))
                    concatenateWords.add(word);
            }
            return concatenateWords;
        }
    
        public void insert(String word) {
            TrieNode node = root;
            int length = word.length();
            for (int i = 0; i < length; i++) {
                int index = word.charAt(i) - 'a';
                if (node.next[index] == null)
                    node.next[index] = new TrieNode();
                node = node.next[index];
            }
            node.wordEnd = true;
        }
    
        public boolean depthFirstSearch(String word, TrieNode node, int count, int start) {
            int length = word.length();
            for (int i = start; i < length; i++) {
                int index = word.charAt(i) - 'a';
                if (node.next[index] == null)
                    return false;
                node = node.next[index];
                if (node.wordEnd && depthFirstSearch(word, root, count + 1, i + 1))
                    return true;
            }
            return count > 0 && node.wordEnd;
        }
    }
    
    class TrieNode {
        boolean wordEnd;
        TrieNode[] next;
    
        public TrieNode() {
            wordEnd = false;
            next = new TrieNode[26];
        }
    }
    
    ############
    
    class Trie {
        Trie[] children = new Trie[26];
        boolean isEnd;
    
        void insert(String w) {
            Trie node = this;
            for (char c : w.toCharArray()) {
                c -= 'a';
                if (node.children[c] == null) {
                    node.children[c] = new Trie();
                }
                node = node.children[c];
            }
            node.isEnd = true;
        }
    }
    
    class Solution {
        private Trie trie = new Trie();
    
        public List<String> findAllConcatenatedWordsInADict(String[] words) {
            Arrays.sort(words, (a, b) -> a.length() - b.length());
            List<String> ans = new ArrayList<>();
            for (String w : words) {
                if (dfs(w)) {
                    ans.add(w);
                } else {
                    trie.insert(w);
                }
            }
            return ans;
        }
    
        private boolean dfs(String w) {
            if ("".equals(w)) {
                return true;
            }
            Trie node = trie;
            for (int i = 0; i < w.length(); ++i) {
                int idx = w.charAt(i) - 'a';
                if (node.children[idx] == null) {
                    return false;
                }
                node = node.children[idx];
                if (node.isEnd && dfs(w.substring(i + 1))) {
                    return true;
                }
            }
            return false;
        }
    }
    
  • // OJ: https://leetcode.com/problems/concatenated-words/
    // Time: O(N * W^2)
    // Space: O(NW)
    struct TrieNode {
        TrieNode *next[26] = {};
        bool end = false;
    };
    class Solution {
        TrieNode root;
        void addWord(TrieNode *node, string &s) {
            for (char c : s) {
                if (!node->next[c - 'a']) node->next[c - 'a'] = new TrieNode();
                node = node->next[c - 'a'];
            }
            node->end = true;
        }
        bool valid(string &s) {
            int N = s.size();
            vector<bool> dp(N + 1);
            dp[0] = true;
            for (int i = 0; i < N && !dp[N]; ++i) {
                if (!dp[i]) continue;
                auto node = &root;
                for (int j = i; j < N - (i == 0); ++j) {
                    node = node->next[s[j] - 'a'];
                    if (!node) break;
                    if (node->end) dp[j + 1] = true;
                }
            }
            return dp[N];
        }
    public:
        vector<string> findAllConcatenatedWordsInADict(vector<string>& A) {
            for (auto &s : A) {
                if (s.empty()) continue;
                addWord(&root, s);
            }
            vector<string> ans;
            for (auto &s : A) {
                if (s.size() && valid(s)) ans.push_back(s);
            }
            return ans;
        }
    };
    
  • class Trie:
        def __init__(self):
            self.children = [None] * 26
            self.is_end = False
    
        def insert(self, w):
            node = self
            for c in w:
                idx = ord(c) - ord('a')
                if node.children[idx] is None:
                    node.children[idx] = Trie()
                node = node.children[idx]
            node.is_end = True
    
    
    class Solution:
        def findAllConcatenatedWordsInADict(self, words: List[str]) -> List[str]:
            def dfs(w):
                if not w:
                    return True
                node = trie
                for i, c in enumerate(w):
                    idx = ord(c) - ord('a')
                    if node.children[idx] is None:
                        return False
                    node = node.children[idx]
                    if node.is_end and dfs(w[i + 1 :]):
                        return True
                return False
    
            trie = Trie()
            ans = []
            words.sort(key=lambda x: len(x))
            for w in words:
                if dfs(w):
                    ans.append(w)
                else:
                    trie.insert(w)
            return ans
    
    ############
    
    class Solution(object):
      def findAllConcatenatedWordsInADict(self, words):
        """
        :type words: List[str]
        :rtype: List[str]
        """
    
        def wordBreak(word, cands):
          if not cands:
            return False
          dp = [False] * (len(word) + 1)
          dp[0] = True
          for i in range(1, len(word) + 1):
            for j in reversed(range(0, i)):
              if not dp[j]:
                continue
              if word[j:i] in cands:
                dp[i] = True
                break
          return dp[-1]
    
        words.sort(key=lambda x: -len(x))
        cands = set(words)
        ans = []
        for i in range(0, len(words)):
          cands -= {words[i]}
          if wordBreak(words[i], cands):
            ans += words[i],
        return ans
    
    
  • type Trie struct {
    	children [26]*Trie
    	isEnd    bool
    }
    
    func newTrie() *Trie {
    	return &Trie{}
    }
    func (this *Trie) insert(word string) {
    	node := this
    	for _, c := range word {
    		c -= 'a'
    		if node.children[c] == nil {
    			node.children[c] = newTrie()
    		}
    		node = node.children[c]
    	}
    	node.isEnd = true
    }
    
    func findAllConcatenatedWordsInADict(words []string) (ans []string) {
    	sort.Slice(words, func(i, j int) bool { return len(words[i]) < len(words[j]) })
    	trie := newTrie()
    	var dfs func(string) bool
    	dfs = func(w string) bool {
    		if w == "" {
    			return true
    		}
    		node := trie
    		for i, c := range w {
    			c -= 'a'
    			if node.children[c] == nil {
    				return false
    			}
    			node = node.children[c]
    			if node.isEnd && dfs(w[i+1:]) {
    				return true
    			}
    		}
    		return false
    	}
    	for _, w := range words {
    		if dfs(w) {
    			ans = append(ans, w)
    		} else {
    			trie.insert(w)
    		}
    	}
    	return
    }
    

All Problems

All Solutions