在Trie操作上找不到这个算法（递归）

有人能帮我理解下面的代码吗？在Trie操作上找不到这个算法（递归）

countWords(vertex, word, missingLetters) 
    k=firstCharacter(word) 
    if isEmpty(word) 
     return vertex.words 
    else if notExists(edges[k]) and missingLetters=0 
     return 0 
    else if notExists(edges[k]) 
     cutLeftmostCharacter(word) 
     return countWords(vertex, word, missingLetters-1) 
     //Here we cut a character but we don't go lower in the tree 
    else 
     //We are adding the two possibilities: the first 
     //character has been deleted plus the first character is present 
     r=countWords(vertex, word, missingLetters-1) 
     cutLeftmostCharacter(word) 
     r=r+countWords(edges[k], word, missingLetters) 
     return r

的想法是，使用Trie我们正在努力寻找一个词出现在我们的字典的次数，但我们可能有丢失的信件。
我迷失在else部分。我不明白这个逻辑。
例如，如果我们的单词的第一个字符是匹配，我们击中最后的else，然后在countWords递归在同一级别，但与missingLetters-1，但然后不是一个完全相同的循环？即它会再次比较同级别中的第一个字母等等？
有人可以帮我解决这个问题吗？

来源

2012-05-25 Jim

即使按照antti.huima的建议反转最后一行的顺序，仍然看起来不太好。

如果我理解正确的话，如果你有Pizza，Lizza也应该算如果missingLetters == 1，对吗？不过，如果Lizza是不是在特里输入

else if notExists(edges['l']) 
     cutLeftmostCharacter(word) # 'izza' left 
     return countWords(vertex, 'izza', 0) #vertex is 'P' I guess

和下次进入

else if notExists(edges['i']) and missingLetters=0

返回0？

鉴于你已经有了一个trie，我建议你看看Levehnstein Distance。

来源

2012-05-25 08:59:25 Pin

该算法是越野车。我怀疑由于某种原因，最后一次调用cutLeftMostCharacter已与前一行进行了交换。如果代码会读取

cutLeftmostCharacter(word) 
    r=countWords(vertex, word, missingLetters-1) 
    r=r+countWords(edges[k], word, missingLetters)

它会更有意义。

来源

2012-05-25 07:14:35

在Trie操作上找不到这个算法（递归）

回答

相关问题