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:

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

Companies:
Amazon, Apple

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

Similar Questions:

Word Break II (Hard)

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
}

472 - Concatenated Words

472. Concatenated Words (Hard)

Solution 1. Trie + C++ Static Pool

Solution 2: Trie + unordered_map

Solution 3. DP

All Problems

All Solutions

Welcome to Subscribe On Youtube

472. Concatenated Words (Hard)

Solution 1. Trie + C++ Static Pool

Solution 2: Trie + unordered_map

Solution 3. DP

All Problems

All Solutions