在字典中找到一个单词，但单词删除了一个字母

Question

我试图理解以下算法，但我很难在几件事上：

首先，输入是什么样的，即aple或ap_le和

其次，代码的部分是什么？

"我们添加了这两种可能性：第一个 角色已被删除，加上第一个角色存在 r=countWords(vertex, word, missingLetters-1)"

如果通过链接到顶点的所有EDEG，则不应该第二秒？

来源：https://www.topcoder.com/community/data-science/data-science-tutorials/using-tries/

countWords(vertex, word, missingLetters)
    k=firstCharacter(word)
    if isEmpty(word)
        return vertex.word
    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 

Answer 1

首先：输入是树中的顶点（root）一个单词和许多缺失的字母。

例如：countwords（rootnode，"苹果"，1）

树是固有的递归，要理解这些算法，您应该将顶点视为在函数的每个后续调用中在树上开始的位置。

现在，我将在平原psudo-er代码中说出此逻辑的每个部分。

countWords(WhereYouAreAt, word, missingLetters)
    k = firstCharacter(word) # the first charactor is the next edge to traverse
    if(word = ""){Return(WhereYouAreAt.word)}
    else if (notExists(edges[k]) and missingLetters=0) {return 0} # Because you arn't at a word and and you can't make a word with the prefix that caused you to arrive at WhereYouAreAt.
    else if notExists(edges[k]){
         cutLeftmostCharacter(word)
         return countWords(vertex, word, missingLetters-1)
         #use one of the missing letters on the current letter. continue from WhereYouAre
    }
    else{
        cutLeftmostCharacter(word) #!!!
        r=countWords(vertex, word, missingLetters-1)
        r=r+countWords(edges[k], word, missingLetters) 
        return r
    }

其次是线路cutleftmostcharacter（word）＃！您需要在行之前询问哪些单词数量在节点下的单词数量，其中包含字母在剩余的单词中的字母中。如果您不跳过该字母，则第一行r =计数，如果您跳过Word中的第一个字母，而R =计数。

不幸的是，由于可能会尝试返回字符串和数字的总和……要解决此问题，我们需要将第一个if语句更改为

，这仍然使输出更加糟糕。

 if(word = ""){Return(vertex.words)}

而不是顶点...

使用此输出应该是字典中的单词数，其中包含来自Word字母的有序子集。

我希望这会有所帮助。