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 --。
继续加油!:)
相似问题