java - 为什么这种迭代的 trie-traversal 不能在查询时产生正确的单词？

Question

所以，这是我的困境:我试图遍历一个 trie 数据结构来找到第 n 个单词。

对于那些不熟悉的人来说，trie 是一种基于压缩的数据结构，它允许您插入一系列单词，并按字典顺序对它们进行排序，但每个节点都是它自己的单独字母，从而分支并拼写成各自的词(如果不清楚，请有更具体定义的人修复!)。

树中的每个节点都有一个包含 26 个节点的数组来表示字母表中的 26 个字母。拼出一个单词后，数组 (isWord) 中该单词最后一个字符的 boolean 值将被标记为真。 {a, and, are, art} 等词中的词也是如此； “a”是一个词，因此，这个字母的 isWord 被设置为 true。但是，“and”中的字母被附加到“a”上，而“d”被标记为单词。

介绍完了，下面是我的问题:我很难递归地做这个，所以我尝试迭代地做。我非常非常接近解决方案，但由于某种原因，当我调用 nthWord(int n) 时，一些单词被跳过了。本质上，该方法应该遍历树(按照 trie 的属性按字母顺序排列)并找到顾名思义的第 n 个单词。但是，如前所述，有时该方法会跳过 trie 中的单词，即使它保证它们被添加到 trie 中(并且 isWord boolean 值也总是正确的)。我已经解决这个问题大约 3 天了，我很迷茫。

我希望输出是序列中的第 n 个单词(来自非常大的 .txt 单词文件)，但有时它会跳过某些单词。如果将 j 分配给 -1，则会考虑以相同字母的 2 开头的单词，例如“aardvark”，但会跳过其他单词。相反，如果它被分配为 0，则其他单词会被计算在内，但以两个相同字母开头的单词将被跳过。

编辑:我还应该声明 nthWord(...) 方法不处理重复的单词。 Trie 存储每个单词在该单词的最后一个字符中出现的频率。因此，在这种情况下，重复的单词不是问题。

Answer 1

下面是这道题的递归解法(比较直观)。只需将其视为树问题，您必须从左到右遍历树并尝试找到第 N 个单词。

您可以从根节点进行 DFS。保留一个变量来存储你到目前为止访问过的单词数(你访问过的带有 isWord 的节点数)。并在到达第 N 个单词时返回该单词。

代码应该是这样的。我刚刚写了一个模板代码 -

def findWord(TrieNode,word):
    global N
    if TrieNode.isWord:
        if N == 0:
            return word
        else:
            N -= 1

    for each in TrieNode.children:
        if each is not None:
            word += each.character
            res = findWord(N,each,word)
            if len(res) > 0:
                return res
            word = word[:-1]
    return ''
N = input()
findWord(root,'')