对于Trie这种数据结构的添加操作结合LeetCode208号问题出现了错误
来源：10-2 Trie字典树基础
南山乔木枝
2018-07-18
下面是我的测试代码：
package facelay.base;
import java.util.TreeMap;
public class Trie {
private class Node {
public boolean isWord;
public TreeMap<Character, Node> next;
public Node(boolean isWord) {
this.isWord = isWord;
this.next = new TreeMap<>();
}
public Node() {
this(false);
}
}
private Node root;
private int size;
public Trie() {
root = new Node();
size = 0;
}
public int getSize() {
return size;
}
// 向Trie中添加一个新的单词word
public void add(String word) {
Node cur = root;
for (int i = 0; i < word.length(); i++) {
char c = word.charAt(i);
if (cur.next.get(c) == null) {
cur.next.put(c, new Node());
} else {
cur = cur.next.get(c);
}
}
if (!cur.isWord) {
cur.isWord = true;
size++;
}
}
// 查询Trie中的某个单词是否存在
public boolean query(String word) {
Node cur = root;
for (int i = 0; i < word.length(); i++) {
char c = word.charAt(i);
if (cur.next.get(c) == null) {
return false;
} else {
cur = cur.next.get(c);
}
}
return cur.isWord;
}
// 查询单词的前缀
public boolean prefix(String word) {
Node cur = root;
for (int i = 0; i < word.length(); i++) {
char c = word.charAt(i);
if (cur.next.get(c) == null) {
return false;
} else {
cur = cur.next.get(c);
}
}
return true;
}
public static void main(String[] args) {
Trie trie = new Trie();
trie.add("aple");
System.out.println(trie.query("aple"));
// System.out.println(trie.query("app"));
// System.out.println(trie.prefix("app"));
// trie.add("app");
// System.out.println(trie.query("app"));
}
}
1回答
-
在你的代码中，for循环里的逻辑不是if else的关系。
不管cur.next里有没有c，都要执行cur= cur.next.get(c)。如果之前cur.next里没有c，我们加上，如果已经有了，那就太好了，不用加了。这个if逻辑执行完，cur.next里一定包含c了，然后我们的cur移到下一个节点，即：cur= cur.next.get(c)
在回顾一下课程中Trie的讲解？
同时，课程的所有代码，都可以在官方github中找到，传送门：https://github.com/liuyubobobo/Play-with-Data-Structures
其中，对于使用我们实现的Trie，完成Leetcode 208号问题的代码，可以参考：https://github.com/liuyubobobo/Play-with-Data-Structures/blob/master/10-Trie/04-Prefix-in-Trie/src/Trie208.java （提交时需要修改类名：）
加油！
012018-07-18
相似问题