0

我正在制作一个 java Trie，我终于完成了，但我正在添加 getWords() 函数，它将返回 Trie 内的所有值。

我有这个功能的问题。快速背景信息：每个字符都有一个“索引”，它实际上是整个单词，包括所有父字符。当您输入单词“soup”时，字母 p 的值为 isWord = true 和 index = “soup”。

此外，您看到的“children”变量是一个 HashMap，此函数位于 TrieNode 类中，因此请记住这一点。

给我带来麻烦的代码：

private List<String> wordList = new ArrayList<String>();

public List<String> getWords(){

   /*Iterate through trie for every value in the hash map.
    Find all words with isWord= true and add that index to wordList
    */

   String word;
   for(Character key : children.keySet()){
       children.get(key).getWords();
       if(children.get(key).isWord == true){
           word = (children.get(key).index);
           wordList.add(word);
           System.out.println(wordList);  //prints list here for test
       }
   }
   System.out.println(wordList);  // prints again for test (second print)
   return wordList;
}

第一个打印语句打印出一个单词，即当 isWord 为真时哈希映射当前所在的当前单词。下一次打印（递归运行时）它再次只打印那个单词。

IE：如果你在 trie "soup" 和 "hello" 中添加两个单词，它会在各自的行上打印：hello 和 soup，但 wordList 在第二次打印整个列表时显然会丢失第一个单词。

我不确定为什么单词会从单词列表中丢失。它应该打印：“你好”第一次和“你好汤”第二次不应该吗？

一旦函数完成，它会返回完全为空且没有任何内容的 wordList。

编辑：

由于混乱，我在这里添加了一些视觉效果。（包括 trie 的所有代码都太没必要了）。

将单词“hello”“hi”“soup”添加到 Trie

给它以下结构

整个 trie 现在有两个键值对。H和S。

H 是密钥，其中包含一个完整的独立 Trie。H 内部是节点 I 和 E（用于 hello 和 hi）

S 节点中有一个 O，O 有一个 U 等等。

递归是必要的，因为您可以遍历哈希映射键并且只获得 S 和 H。我也需要 THOSE 节点的键，所以我递归地执行此操作。

在这些前缀的末尾最终将是单词。一旦我找到这个词，我想将它添加到 wordList 中。

最后我想最终返回 wordList

4

1 回答 1

1

这并不是真正的递归，因为您调用getWords的是对象的不同实例而不是this. 在评论中，fge指出结果被忽略是正确的。本质上，您最终会在对象图中的每个级别上得到单独的列表，其中一个对象只有它的直接后代的话。纠正此问题的一种方法是List在顶层创建 并将其传递给方法getWords并让每个元素将其单词添加到该List。

于 2013-06-17T18:21:32.607 回答