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再帰しますが、それは同一のループではありませんか? つまり、同じレベルの最初の文字などを再度比較しますか? 誰かがこれを理解するのを手伝ってくれませんか?countWordsmissingLetters-1

4

2 に答える 2

0

最後の行の順序がantti.huimaで示唆されているように反転されていたとしても、私にはまだ何かがうまく見えません.

私がそれを正しく理解していれば、あなたが持っているPizza場合Lizza、missingLetters==1の場合もカウントする必要がありますよね? ただし、リザがトライにいない場合は、入力します

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を返しますか?

すでにトライをお持ちの方は、レーベンシュタイン距離をご覧になることをお勧めします。

于 2012-05-25T08:59:25.453 に答える
0

アルゴリズムにバグがあります。何らかの理由で、cutLeftMostCharacter への最後の呼び出しが前の行と交換されていると思われます。コードが読める場合

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

それはより理にかなっています。

于 2012-05-25T07:14:35.470 に答える