##### 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.
// 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:
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:
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:
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();

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))
}
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();

Arrays.sort(words, (a, b) -> a.length() - b.length());
List<String> ans = new ArrayList<>();
for (String w : words) {
if (dfs(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:
for (auto &s : A) {
if (s.empty()) continue;
}
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):
"""
: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
}