Trie, remove method

来源:2-7 更多和Trie字典树相关的话题

慕用8103342

2021-10-16 13:19:28

Trie中刪除操作邏輯,以下代碼是否有誤?

public void remove(String word) {
    if (contains(word)) {
        remove(root, word, 0);
    }
}
private Node remove(Node node, String word, int index) {
    if (index == word.length()) {
        size--;
        node.isWord = false;
        return (node.next.size() == 0) ? null : node;
    }
    char c = word.charAt(index);
    node.next.put(c, remove(node.next.get(c), word, index+1));
    if (node.next.get(c) == null) {
        node.next.remove(c);
    }
    return node;
}


写回答

1回答

liuyubobobo

2021-10-18

赞!没有问题,是正确的。


值得一提的是,你现在的算法,先判断是否存在 word,再删除,实际上搜索了两趟。这两趟可以合一,直接在 remove 的过程中完成。但如果这样做,在递归的 remove 中,index  == word.length 的时候,就要判断一下 node.isWord 是否为 true,为true 的时候才 size --。


继续加油!:)

0

算法与数据结构

波波老师5年集大成之作,算法与数据结构系统学习,考试、面试、竞赛通用

2610 学习 · 1087 问题

查看课程