第 2 节 Trie 的添加与查询

Trie 的添加操作

基本思想：从上到下，先查询，如果没有就添加。

参考代码：

public void add(String word) {
    // root 是当前 Trie 对象的属性
    Node currNode = root;
    for (int i = 0; i < word.length(); i++) {
        Character c = word.charAt(i);
        if (currNode.next.get(c) == null) {
            currNode.next.put(c, new Node());
        }
        currNode = currNode.next.get(c);
    }
    // 如果已经添加过，才将 size++
    if (!currNode.isWord) {
        currNode.isWord = true;
        size++;
    }
}

Trie 的查询操作

理解：Trie 的查询只与 待查询的字符串的长度 有关。

下面这个方法查询整个单词在 Trie 中是否存在，所以在路径匹配完成以后，一定不要忘了判断匹配到的那个结点的 isWord 属性，如果它是一个单词的结尾，才返回 True。

参考代码：

public boolean contains(String word){
    Node currNode = root;
    Character currC;
    for (int i = 0; i < word.length(); i++) {
        currC = word.charAt(i);
        if (currNode.next.get(currC) == null) {
            return false;
        }
        currNode = currNode.next.get(currC);
    }
    return currNode.isWord;
}

---

作者：liweiwei1419 链接：https://suanfa8.com/trie/add-and-search 来源：算法吧 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。