使用尝试递归地在哈希图中查找单词

Question

我的方法应该将关联的 key/value 对添加到 trie 中，如果键已经在 trie 中，则应该更新值。但是我不太确定我做错了什么，这是我第一次尝试。所以我目前正在研究我的 put 方法，我有以下内容：

public void put(TrieMapNode current, String curKey, String value){
if(current.getChildren().containsKey(curKey))
      value = current.get(key);
      curKey =value;

  put(current.getChildren().get(curKey), curKey, value);

}

如有任何帮助，我们将不胜感激！

Answer 1

在您当前的实施中，您不会受益于 trie 的优势。那是因为在根节点，遇到的每个字符串都有一个子节点。
那不是构建 trie 的方式。 trie 的每个节点每个字符最多可以有一个子节点（构成字符串的元素）。
所以你的方法应该更像下面这样：

public void put(TrieMapNode current, String key, String value, int depth){
if (depth == key.length()){
   current.value = value;
} else {
    char curChar = key.charAt(depth);
    if(!current.getChildren().containsKey(curChar)){
        TrieMapNode newNode = new TrieMapNode();
        current.getChildren().put(curChar, newNode);
    }
    put(current.getChildren().get(curChar), curKey, value, depth + 1);
}

您犯的主要错误是在您的 trie 中 inserting/updating 时将密钥视为一个整体。这将导致一个根节点对于地图中的每个键都有一个子节点（因此有很多子节点），但深度非常有限（根节点、它的子节点等等）。

在我建议的实现中，一个节点每个可能的字符都有一个子节点（有界数字，26、52，无论如何都是一个小而有界的数字）。
而且它的深度不限于一个，因为正如你在 else 块中看到的那样，如果我们要查找的节点不存在，我们会创建一个节点（当你开始时你只有一个根节点，所以你需要计划创建新节点的情况），我们还在当前节点的子节点上递归调用 put 。因此，该值将存储在等于其键长度的深度。

使用尝试递归地在哈希图中查找单词

Recursively finding words in a hashmap using tries

java

hashmap

trie