通过从长度为 n 的单词中添加一个额外的字母来查找长度为 n+1 的所有单词

Question

我有几个由数千个单词组成的长列表，按长度排序，每个单词长度一个列表。对于列表中长度为 n 的每个单词，我想生成列表中长度为 n+1 的所有单词，只需添加一个额外的字母即可。

通过反复试验，我发现了一些可以完成这项工作的东西，但它很混乱并且运行了很长时间，因为我对 Python 很陌生。我在处理重复字母的所有变体时遇到了很大的困难……有什么更好、更有效的方法来完成工作？

    SevenPlusOneList = []
    for word7 in ListOfSevens:
        SevenPlusOne = []
        SevenCount = collections.Counter(word7)
            for word8 in ListOfEights:
            EightCount = collections.Counter(word8)
            NotSharedLetters = {k: SevenCount[k] for k in EightCount if 
            k in EightCount and SevenCount[k] != EightCount[k]}
            if len(NotSharedLetters) == 1 and len(EightCount) >= 
                len(SevenCount) and (len(EightCount)-len(SevenCount)==1 
            or list(NotSharedLetters)[0] in SevenCount):
                SevenPlusOne.append(word8)
            if len(SevenPlusOne) > 0:
                SevenPlusOneList.append(SevenPlusOne)
            else:
                SevenPlusOneList.append('-')

Answer 1

这个程序与你的程序具有相同的时间复杂度，所以它可能会更快或更慢。时间复杂度为：

O(m×n)

。 它使用一个名为 PyDictionary 的 Python 模块，每当它找不到特定单词的含义时，它就会返回 None。 这是我写的程序：

from PyDictionary import PyDictionary # A dictionary for Python that can find meanings (and validate words)

dictionary: PyDictionary = PyDictionary() # Create a new class object "dictionary"

word7: list[str] = ["questin"] # Just an example
alphabet: list[str] = [
    "a", "b", "c", "d", "e", "f", "g",
    "h", "i", "j", "k", "l", "m", "n",
    "o", "p", "q", "r", "s", "t", "u",
    "v", "w", "x", "y", "z"
]

valid_words: list[str] = []

for word in word7:
    for index, _character in enumerate(word): # Used prefix underscore because _character isn't used
        for letter in alphabet:
            try:
                new_word = word[0:index + 1] + letter + word[index+1:len(word)]
                if dictionary.meaning(new_word): # If a meaning is found for a word, then proceed
                    valid_words.append(new_word)
            except Exception as e: # If it gets an Exception, that most likely means that the word doesn't exist
                pass # Skip

print(valid_words)