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
| class Solution {
private String res;
private static class Node {
Map<Character, Node> children;
boolean isWord;
Node(Map<Character, Node> _children) {
this.children = _children;
isWord = false;
}
}
private void addWord(Node root, String word) {
Node ptr = root;
for (char letter : word.toCharArray()) {
ptr.children.putIfAbsent(letter, new Node(new HashMap<>()));
ptr = ptr.children.get(letter);
}
ptr.isWord = true;
}
private void dfs(Node node, StringBuilder curr) {
boolean hasLongerWord = false;
for (Map.Entry<Character, Node> entry : node.children.entrySet()) {
if (entry.getValue().isWord) {
curr.append(entry.getKey());
dfs(entry.getValue(), curr);
hasLongerWord = true;
curr.setLength(curr.length() - 1);
}
}
if (!hasLongerWord) {
if (curr.length() > res.length() || (curr.length() == res.length() && curr.toString().compareTo(res) < 0)) {
res = curr.toString();
}
}
}
public String longestWord(String[] words) {
Node root = new Node(new HashMap<>());
for (String word : words) {
addWord(root, word);
}
res = "";
dfs(root, new StringBuilder());
return res;
}
}
|
使用Trie把每个word存起来. 然后backtrack, 只走node被标记为word的地方. 直到走不动. 如何知道走不动? 我使用了一个flag, 如果往下走了, 这个flag是true, 否则就是false. 于是这样能cover到两种走不动的情况: 一种是没有child了, 一种是下面的child都不是word. 遇到flag是false时, 我们就要看当前的word是否比res长或者如果和res一样长是否比它更靠前.
