Question

有人能帮助我理解下面的黄道码吗?

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

The idea is that using a Trie we are trying to find the number of times a word appears in our dictionary, BUT we may have missing letters.
I am lost in the else part. I don t understand the logic.
For example if the first char of our word is a match we hit the last else and then recurse on countWords in the same level but with missingLetters-1 but then isn t that an identical loop? I.e. it will compare again the first letter in the same level and so on?
Could someone please help me figure this out?

Answer 1

即使最后几行的顺序按照 Antti.huima 的建议被颠倒了, 有些事情在我看来还是不太对劲。

如果我理解正确, 如果你有 < code> Pizza , < code> Lizza 也应该算漏掉Lizza < /code > 的Letters =1 =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距离。

Answer 2

算法是错误的。我怀疑由于某种原因, 最后的切切“ MostCharacter ” 的电话已经和前一行进行了交换。如果代码会读的话

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

这会更有意义。

友情链接