0

有人可以帮我理解以下 pheudocode 吗？ 

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但是这不是一个相同的循环吗？即它会再次比较同一级别的第一个字母等等？
有人可以帮我解决这个问题吗？

4

2 回答 2

0

该算法是错误的。我怀疑由于某种原因，对 cutLeftMostCharacter 的最后一次调用已与前一行交换。如果代码会读取

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

这会更有意义。

于 2012-05-25T07:14:35.470 回答
0

即使按照 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？

鉴于您已经尝试过，我建议您看一下Levehnstein Distance。

于 2012-05-25T08:59:25.453 回答