Python-什么词可以删除最多的连续字母并且仍然是字典有效词？

Question

我使用这个可怕且低效的实现来找到可以删除最连续的最后一个字母并且仍然是一个单词的单词。

比如Rodeo，就是大家熟知的:Rodeo，Rode，Rod，Ro。 该程序找到了“ Composer ”: Composer 、 Composer 、 Composer 、 Composer 、 Composer

我想知道我应该如何着手创建一个程序来找到最长的单词，该单词可以删除任何字母(不仅仅是最后一个字母)并且仍然被认为是一个单词:

例如:beast、best、bet、be -- 都是有效的可能性

这是我的程序，用于查找删除连续字母的程序(我也有兴趣了解如何改进和优化它):

#Recursive function that finds how many letters can be removed from a word and
#it still be valid.  
def wordCheck(word, wordList, counter):

    if len(word)>=1:
        if word in wordList:
            return (wordCheck(word[0:counter-1], wordList, counter-1))
        else:
            return counter
    return counter


def main():
    a = open('C:\\Python32\\megalist2.txt', 'r+')
    wordList = set([line.strip() for line in a])
    #megaList contains a sorted list of tuple of 
    #(the word, how many letters can be removed  consecutively)
    megaList = sorted([(i, len(i)-1- wordCheck(i, wordList, len(i))) for i in wordList], key= lambda megaList: megaList[1])


    for i in megaList:
        if i[1] > 3:
            print (i)

if __name__ == '__main__':
    main()

Answer 1

for each english word W:
    for each letter you can remove:
        remove the letter
        if the result W' is also word:
            draw a line W->W'
for each english word W:
    connect ROOT-> each english word W
use a graph search algorithm to find the longest path starting at ROOT
    (specifically, the words are now in a directed acyclic graph; traverse
    the graph left-right-top-down, i.e. in a "topological sort", keeping
    track of the longest candidate path to reach each node; this achieves 
    the result in linear time)

这个算法只需要线性的 O(#wordsInEnglish*averageWordLength) 时间!基本上只要读取输入就可以了

它可以很容易地修改以找到删除的连续字母:而不是像 (Node('rod').candidate = rodeo->rode->rod 这样每个节点保留一个候选者)，为每个节点保留一系列候选者以及您为获得每个候选者而删除的字母的索引 (Node('rod').candidates={rodeo->rod|e->rod|, road->ro|d}).这具有相同的运行时间。