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回答
赞!没有问题,是正确的。
值得一提的是,你现在的算法,先判断是否存在 word,再删除,实际上搜索了两趟。这两趟可以合一,直接在 remove 的过程中完成。但如果这样做,在递归的 remove 中,index == word.length 的时候,就要判断一下 node.isWord 是否为 true,为true 的时候才 size --。
继续加油!:)
相似问题