Problem#
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 necessarily distinct) in the given array.
Examples#
Example 1:
1
2
3
4
5
|
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:
1
2
|
Input: words = ["cat","dog","catdog"]
Output: ["catdog"]
|
Solution#
Method 1 – Dynamic Programming with Word Break#
Intuition#
The key idea is to check for each word if it can be formed by concatenating at least two shorter words from the list. We use dynamic programming (similar to the classic Word Break problem) to efficiently check if a word can be split into valid subwords.
Approach#
- Store all words in a set for O(1) lookup.
- For each word, temporarily remove it from the set to avoid using itself.
- Use DP to check if the word can be formed by concatenating other words in the set.
- If yes, add it to the answer list.
- Restore the word in the set after checking.
C++#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
|
class Solution {
public:
bool canForm(string &w, unordered_set<string> &st) {
if (st.empty()) return false;
int n = w.size();
vector<bool> dp(n+1, false);
dp[0] = true;
for (int i = 1; i <= n; ++i) {
for (int j = (i==n?1:0); j < i; ++j) {
if (dp[j] && st.count(w.substr(j, i-j))) {
dp[i] = true;
break;
}
}
}
return dp[n];
}
vector<string> findAllConcatenatedWordsInADict(vector<string>& words) {
unordered_set<string> st(words.begin(), words.end());
vector<string> ans;
for (auto &w : words) {
st.erase(w);
if (canForm(w, st)) ans.push_back(w);
st.insert(w);
}
return ans;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
|
func findAllConcatenatedWordsInADict(words []string) []string {
st := make(map[string]bool)
for _, w := range words {
st[w] = true
}
var ans []string
var canForm func(string) bool
canForm = func(w string) bool {
n := len(w)
if len(st) == 0 {
return false
}
dp := make([]bool, n+1)
dp[0] = true
for i := 1; i <= n; i++ {
for j := 0; j < i; j++ {
if i == n && j == 0 {
continue
}
if dp[j] && st[w[j:i]] {
dp[i] = true
break
}
}
}
return dp[n]
}
for _, w := range words {
delete(st, w)
if canForm(w) {
ans = append(ans, w)
}
st[w] = true
}
return ans
}
|
Java#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
|
class Solution {
public List<String> findAllConcatenatedWordsInADict(String[] words) {
Set<String> st = new HashSet<>(Arrays.asList(words));
List<String> ans = new ArrayList<>();
for (String w : words) {
st.remove(w);
if (canForm(w, st)) ans.add(w);
st.add(w);
}
return ans;
}
private boolean canForm(String w, Set<String> st) {
if (st.isEmpty()) return false;
int n = w.length();
boolean[] dp = new boolean[n+1];
dp[0] = true;
for (int i = 1; i <= n; ++i) {
for (int j = (i==n?1:0); j < i; ++j) {
if (dp[j] && st.contains(w.substring(j, i))) {
dp[i] = true;
break;
}
}
}
return dp[n];
}
}
|
Kotlin#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
|
class Solution {
fun findAllConcatenatedWordsInADict(words: Array<String>): List<String> {
val st = words.toHashSet()
val ans = mutableListOf<String>()
for (w in words) {
st.remove(w)
if (canForm(w, st)) ans.add(w)
st.add(w)
}
return ans
}
private fun canForm(w: String, st: Set<String>): Boolean {
if (st.isEmpty()) return false
val n = w.length
val dp = BooleanArray(n+1)
dp[0] = true
for (i in 1..n) {
for (j in if (i==n) 1 else 0 until i) {
if (dp[j] && st.contains(w.substring(j, i))) {
dp[i] = true
break
}
}
}
return dp[n]
}
}
|
Python#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
class Solution:
def findAllConcatenatedWordsInADict(self, words: list[str]) -> list[str]:
st: set[str] = set(words)
ans: list[str] = []
def can_form(w: str) -> bool:
n = len(w)
if not st:
return False
dp: list[bool] = [False] * (n+1)
dp[0] = True
for i in range(1, n+1):
for j in (range(1, i) if i == n else range(i)):
if dp[j] and w[j:i] in st:
dp[i] = True
break
return dp[n]
for w in words:
st.remove(w)
if can_form(w):
ans.append(w)
st.add(w)
return ans
|
Rust#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
|
impl Solution {
pub fn find_all_concatenated_words_in_a_dict(words: Vec<String>) -> Vec<String> {
use std::collections::HashSet;
let mut st: HashSet<&str> = words.iter().map(|w| w.as_str()).collect();
let mut ans = Vec::new();
for w in &words {
st.remove(w.as_str());
if can_form(w, &st) {
ans.push(w.clone());
}
st.insert(w.as_str());
}
ans
}
}
fn can_form(w: &str, st: &std::collections::HashSet<&str>) -> bool {
let n = w.len();
if st.is_empty() { return false; }
let bytes = w.as_bytes();
let mut dp = vec![false; n+1];
dp[0] = true;
for i in 1..=n {
for j in if i == n { 1 } else { 0 }..i {
if dp[j] && st.contains(&w[j..i]) {
dp[i] = true;
break;
}
}
}
dp[n]
}
|
Complexity#
- ⏰ Time complexity:
O(n*L^2), where n is the number of words and l is the average word length.
- 🧺 Space complexity:
O(n*l) for the set and DP array
Method 2 – Trie-Based DFS#
Intuition#
The main idea is to use a Trie to efficiently store all words and then, for each word, check if it can be formed by concatenating at least two shorter words from the Trie. The Trie allows fast prefix lookups, and DFS helps explore all possible splits.
Approach#
- Build a Trie with all words.
- For each word, use DFS to check if it can be split into at least two valid words from the Trie.
- While traversing, whenever a prefix is found in the Trie, recursively check the remaining substring.
- Ensure that the word is not formed by itself alone.
- Collect all words that satisfy the condition.
C++#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
|
class Trie {
public:
Trie* children[26] = {};
bool isWord = false;
};
class Solution {
Trie* root = new Trie();
void insert(const string& w) {
Trie* node = root;
for (char c : w) {
if (!node->children[c-'a']) node->children[c-'a'] = new Trie();
node = node->children[c-'a'];
}
node->isWord = true;
}
bool dfs(const string& w, int idx, int cnt) {
Trie* node = root;
for (int i = idx; i < w.size(); ++i) {
if (!node->children[w[i]-'a']) return false;
node = node->children[w[i]-'a'];
if (node->isWord) {
if (i == w.size()-1) return cnt >= 1;
if (dfs(w, i+1, cnt+1)) return true;
}
}
return false;
}
public:
vector<string> findAllConcatenatedWordsInADict(vector<string>& words) {
for (auto& w : words) if (!w.empty()) insert(w);
vector<string> ans;
for (auto& w : words) {
if (w.empty()) continue;
if (dfs(w, 0, 0)) ans.push_back(w);
}
return ans;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
|
type Trie struct {
children [26]*Trie
isWord bool
}
func insert(root *Trie, w string) {
node := root
for _, c := range w {
idx := c - 'a'
if node.children[idx] == nil {
node.children[idx] = &Trie{}
}
node = node.children[idx]
}
node.isWord = true
}
func dfs(root *Trie, w string, idx, cnt int) bool {
node := root
for i := idx; i < len(w); i++ {
c := w[i] - 'a'
if node.children[c] == nil {
return false
}
node = node.children[c]
if node.isWord {
if i == len(w)-1 {
return cnt >= 1
}
if dfs(root, w, i+1, cnt+1) {
return true
}
}
}
return false
}
func findAllConcatenatedWordsInADict(words []string) []string {
root := &Trie{}
for _, w := range words {
if len(w) > 0 {
insert(root, w)
}
}
var ans []string
for _, w := range words {
if len(w) > 0 && dfs(root, w, 0, 0) {
ans = append(ans, w)
}
}
return ans
}
|
Java#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
|
class Solution {
static class Trie {
Trie[] ch = new Trie[26];
boolean word = false;
}
Trie root = new Trie();
void insert(String w) {
Trie node = root;
for (char c : w.toCharArray()) {
int idx = c - 'a';
if (node.ch[idx] == null) node.ch[idx] = new Trie();
node = node.ch[idx];
}
node.word = true;
}
boolean dfs(String w, int idx, int cnt) {
Trie node = root;
for (int i = idx; i < w.length(); i++) {
int c = w.charAt(i) - 'a';
if (node.ch[c] == null) return false;
node = node.ch[c];
if (node.word) {
if (i == w.length()-1) return cnt >= 1;
if (dfs(w, i+1, cnt+1)) return true;
}
}
return false;
}
public List<String> findAllConcatenatedWordsInADict(String[] words) {
for (String w : words) if (!w.isEmpty()) insert(w);
List<String> ans = new ArrayList<>();
for (String w : words) {
if (!w.isEmpty() && dfs(w, 0, 0)) ans.add(w);
}
return ans;
}
}
|
Kotlin#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
|
class Solution {
class Trie {
val ch = Array<Trie?>(26) { null }
var word = false
}
val root = Trie()
fun insert(w: String) {
var node = root
for (c in w) {
val idx = c - 'a'
if (node.ch[idx] == null) node.ch[idx] = Trie()
node = node.ch[idx]!!
}
node.word = true
}
fun dfs(w: String, idx: Int, cnt: Int): Boolean {
var node = root
for (i in idx until w.length) {
val c = w[i] - 'a'
if (node.ch[c] == null) return false
node = node.ch[c]!!
if (node.word) {
if (i == w.length-1) return cnt >= 1
if (dfs(w, i+1, cnt+1)) return true
}
}
return false
}
fun findAllConcatenatedWordsInADict(words: Array<String>): List<String> {
for (w in words) if (w.isNotEmpty()) insert(w)
val ans = mutableListOf<String>()
for (w in words) {
if (w.isNotEmpty() && dfs(w, 0, 0)) ans.add(w)
}
return ans
}
}
|
Python#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
|
class Trie:
def __init__(self):
self.ch: dict[str, Trie] = {}
self.word: bool = False
class Solution:
def findAllConcatenatedWordsInADict(self, words: list[str]) -> list[str]:
root = Trie()
def insert(w: str) -> None:
node = root
for c in w:
if c not in node.ch:
node.ch[c] = Trie()
node = node.ch[c]
node.word = True
def dfs(w: str, idx: int, cnt: int) -> bool:
node = root
for i in range(idx, len(w)):
c = w[i]
if c not in node.ch:
return False
node = node.ch[c]
if node.word:
if i == len(w)-1:
return cnt >= 1
if dfs(w, i+1, cnt+1):
return True
return False
for w in words:
if w:
insert(w)
ans: list[str] = []
for w in words:
if w and dfs(w, 0, 0):
ans.append(w)
return ans
|
Rust#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
|
struct Trie {
children: [Option<Box<Trie>>; 26],
is_word: bool,
}
impl Trie {
fn new() -> Self {
Self { children: Default::default(), is_word: false }
}
fn insert(&mut self, w: &str) {
let mut node = self;
for b in w.bytes() {
let idx = (b - b'a') as usize;
node = node.children[idx].get_or_insert_with(|| Box::new(Trie::new()));
}
node.is_word = true;
}
fn dfs(&self, w: &[u8], idx: usize, cnt: usize) -> bool {
let mut node = self;
for i in idx..w.len() {
let c = (w[i] - b'a') as usize;
match &node.children[c] {
Some(child) => node = child,
None => return false,
}
if node.is_word {
if i == w.len()-1 {
return cnt >= 1;
}
if self.dfs(w, i+1, cnt+1) {
return true;
}
}
}
false
}
}
impl Solution {
pub fn find_all_concatenated_words_in_a_dict(words: Vec<String>) -> Vec<String> {
let mut root = Trie::new();
for w in &words {
if !w.is_empty() {
root.insert(w);
}
}
let mut ans = Vec::new();
for w in &words {
if !w.is_empty() && root.dfs(w.as_bytes(), 0, 0) {
ans.push(w.clone());
}
}
ans
}
}
|
Complexity#
- Time complexity:
O(n * l^2), where n is the number of words and l is the average word length (due to DFS for each word and Trie traversal).
- Space complexity:
O(n * l) for the Trie and recursion stack.