05 August 2008
给定一个 不含重复 单词的字符串数组 words ，返回 words 中的所有 连接词 。
连接词 的定义为：一个字符串完全是由至少两个给定数组中的单词组成的。
Trie + DFS
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
56
57
58
59
60
61
62
63
64
65
66
67
68
class Solution {
class Trie {
private boolean isEnd;
private Trie[] next;
public Trie(){
isEnd = false;
next = new Trie[26];
}
}
Trie root;
// 向字典树加入单词
public void add(String word){
Trie curNode = root;
for (int i = 0;i < word.length(); i++){
int index = word.charAt(i) - 'a';
if (curNode.next[index] == null) curNode.next[index] = new Trie();
curNode = curNode.next[index];
}
curNode.isEnd = true;
}
// 向字典树搜索单词: search(要搜索的单词， 当前搜索到了哪一位字母， 目前已经由num个单词组成， 字典树引用)
public boolean search(String word, int start, int num, Trie curNode){
// 若已经遍历完，则判断已经遍历单词数大于等于2
if (start == word.length()) {
return num >= 2;
}
// 开始遍历
for (int i = start; i < word.length(); i++){
int index = word.charAt(i) - 'a';
// 当且遇到的字符不匹配，则返回false（因为这证明已遍历完的结果并没有返回true，所以可以直接返回）
if (curNode.next[index] == null) return false;
curNode = curNode.next[index];
// 遍历到最后一个字符时判断是否是单词结尾，若是则假设找到一个单词并继续搜索
if (curNode.isEnd && search(word, i + 1, num + 1, root)){
return true;
}
}
// 遍历完后没有遇到单词结尾
return false;
}
public List<String> findAllConcatenatedWordsInADict(String[] words) {
// 从短到长进行搜索
Arrays.sort(words, (a,b)->(a.length() - b.length()));
root = new Trie();
List<String> res = new ArrayList<>();
for (String word : words) {
// 搜索到对应结果之后将单词加入结果
if (search(word, 0, 0, root)){
res.add(word);
}
// 将这个单词加入字典树
add(word);
}
return res;
}
}