词搜索的递归函数

Question

给定字母：字母示例

letters = 'hutfb' 

我得到了一份包含单词表的文件。在

我需要写一个递归函数，它允许我检查字母所能产生的所有可能性。如果可能在文件中的单词列表中，我需要打印该特定单词。在

所以给你的信

他们可以创造出以下词语：

• a
• 猫
• 空调
• 行动
• 驾驶室

以此类推

每一个字母组合我都需要检查文件，看看它是否是一个有效的单词。如果是的话，我需要打印出来。在

我不知道怎么开始写这个函数。在

Answer 1

不幸的是，我现在不能帮助递归函数，但鉴于更高数量的字母/字符很容易爆炸成数十亿个潜在的组合，如果不在创建过程中过滤，我有一个奇怪的选择，通过迭代已知的单词。不管怎样，这些都要记在记忆里。在

[EDIT]删除了排序，因为它没有真正提供任何好处，修复了迭代时我错误地设置为true的问题

# Some letters, separated by space
letters = 'c a t b'
# letters = 't t a c b'

# # Assuming a word per line, this is the code to read it
# with open("words_on_file.txt", "r") as words:
#     words_to_look_for = [x.strip() for x in words]
#     print(words_to_look_for)

# Alternative for quick test
known_words = [
    'cat',
    'bat',
    'a',
    'cab',
    'superman',
    'ac',
    'act',
    'grumpycat',
    'zoo',
    'tab'
]

# Create a list of chars by splitting
list_letters = letters.split(" ")

for word in known_words:
    # Create a list of chars
    list_word = list(word)
    if len(list_word) > len(list_letters):
        # We cannot have longer words than we have count of letters
        # print(word, "too long, skipping")
        continue

    # Now iterate over the chars in the word and see if we have
    # enough chars/letters
    temp_letters = list_letters[:]

    # This was originally False as default, but if we iterate over each
    # letter of the word and succeed we have a match
    found = True
    for char in list_word:
        # print(char)
        if char in temp_letters:
            # Remove char so it cannot match again
            # list.remove() takes only the first found
            temp_letters.remove(char)
        else:
            # print(char, "not available")
            found = False
            break

    if found is True:
        print(word)

您可以从itertoolsdocumentation复制并粘贴一个product函数，并使用extractSpecie提供的代码，它没有进一步的依赖关系，但是我发现在不做任何调整的情况下，它会返回所有可能的选项，包括我无法立即理解的字符重复。在

^{pr2}$

Answer 2

我同意@dparolin关于处理words文件以查看单词是否符合字母，不生成可能的单词并查看它们是否在文件中。这使得我们不需要将文件读入内存，因为我们一次只需要检查一个单词。它可以通过递归测试来完成：

letters = 'catbt'

def is_match(letters, word):

    if not word:
        return True

    if not letters:
        return False

    letter = letters.pop()

    if letter in word:
        word.remove(letter)

    return is_match(letters, word)

with open('words.txt') as words:
    for word in words:
        word = word.strip()

        if is_match(list(letters), list(word)):
            print(word)

示例用法

^{pr2}$

我们应该能够处理大量的信件而没有问题。在

Answer 3

import itertools
str = "c a t b"
letters = list(str.replace(" ",""))
words_to_look_for = []

for index, letter in enumerate(letters):
    keywords = [''.join(i) for i in itertools.product(letters, repeat = index+1)]
    words_to_look_for.extend(keywords)

print(words_to_look_for)

https://stackoverflow.com/questions/7074051/....