472 Concatenated Words

Search…
472. Concatenated Words​
1. Question
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:
1
Input: ["cat","cats","catsdogcats","dog","dogcatsdog","hippopotamuses","rat","ratcatdogcat"]
2
​
3
​
4
Output: ["catsdogcats","dogcatsdog","ratcatdogcat"]
5
​
6
​
7
Explanation:
8
"catsdogcats" can be concatenated by "cats", "dog" and "cats"; 
9
​
10
"dogcatsdog" can be concatenated by "dog", "cats" and "dog"; 
11
​
12
"ratcatdogcat" can be concatenated by "rat", "cat", "dog" and "cat".
Copied!
Note:
1.The number of elements of the given array will not exceed10,000
2.The length sum of elements in the given array will not exceed600,000.
3.All the input string will only include lower case letters.
4.The returned elements order does not matter.
2. Implementation
(1) Trie + DFS
1
class Solution {
2
    class TrieNode {
3
        char val;
4
        boolean isWord;
5
        TrieNode childNode[];
6
​
7
        public TrieNode() {
8
            childNode = new TrieNode[26];
9
        }
10
    }
11
​
12
    class Trie {
13
        TrieNode root;
14
​
15
        public Trie() {
16
            root = new TrieNode();
17
        }
18
​
19
        public void add(String word) {
20
            if (word == null || word.length() == 0) {
21
                return;
22
            }
23
​
24
            TrieNode curNode = root;
25
​
26
            for (char c : word.toCharArray()) {
27
                int index = c - 'a';
28
​
29
                if (curNode.childNode[index] == null) {
30
                    curNode.childNode[index] = new TrieNode();
31
                    curNode.childNode[index].val = c;
32
                }
33
                curNode = curNode.childNode[index];
34
            }
35
            curNode.isWord = true;
36
        }
37
​
38
        public boolean search(String word) {
39
            if (word == null || word.length() == 0) {
40
                return false;
41
            }
42
​
43
            TrieNode curNode = root;
44
​
45
            for (char c : word.toCharArray()) {
46
                int index = c - 'a';
47
​
48
                if (curNode.childNode[index] == null) {
49
                    return false;
50
                }
51
                curNode = curNode.childNode[index];
52
            }
53
            return curNode.isWord;
54
        }
55
    }
56
​
57
    public List<String> findAllConcatenatedWordsInADict(String[] words) {
58
        List<String> res = new ArrayList<>();
59
​
60
        if (words == null || words.length == 0) {
61
            return res;
62
        }
63
​
64
        Trie trie = new Trie();
65
​
66
        for (String word : words) {
67
            trie.add(word);
68
        }
69
​
70
        for (String word : words) {
71
            if (isConcatenatedWord(word, 0, 0, trie)) {
72
                res.add(word);
73
            }
74
        }
75
        return res;
76
    }
77
​
78
    public boolean isConcatenatedWord(String word, int index, int count, Trie trie) {
79
        // If we are at the end of the current word, check if count is equal to or greater than 1
80
        // A concatenated word should consist of at least two words
81
        if (index == word.length() && count >= 2) {
82
            return true;
83
        }
84
​
85
        TrieNode curNode = trie.root;
86
​
87
        for (int i = index; i < word.length(); i++) {
88
            int pos = word.charAt(i) - 'a';
89
​
90
            if (curNode.childNode[pos] == null) {
91
                return false;
92
            }
93
​
94
            // if word[0...i] && word[i+1...n] are found in dict, then the current word is concatenated word
95
            if (curNode.childNode[pos].isWord) {
96
                if (isConcatenatedWord(word, i + 1, count + 1, trie)) {
97
                    return true;
98
                }
99
            }
100
            curNode = curNode.childNode[pos];
101
        }
102
        return false;
103
    }
104
}
Copied!
3. Time & Space Complexity
Trie + DFS：时间复杂度O(n * L^2)， n为word的个数，l为每个word的平均长度, 空间复杂度O(nL)
421 Maximum XOR of Two Numbers in an Array
642 Design Search Autocomplete System
Last modified 2yr ago
Copy link
Contents
472. Concatenated Words
1. Question
2. Implementation
3. Time & Space Complexity
472. Concatenated Words​

1. Question

2. Implementation

3. Time & Space Complexity

472. Concatenated Words
