python - 从字典中查找句子字谜的有效方法？

Question

我需要编写一个程序，将一个包含字典和任意字符串的文件作为输入，然后输出该字典中构成给定字符串的字谜的所有单词组合。例如，使用 100 个最流行的英语单词和字符串 "i not work"，我应该得到类似于 [' on it work', 'into work', '不是我工作'，'知道或它'，'不工作'，'工作']，我做。

问题是我的程序效率太低:字典中有 100 个单词，字符串长度的实际限制是 7 个字符，之后的所有内容都需要很长时间。我尝试寻找与此事相关的各种算法无济于事。

以下是我搜索字谜的方法:

def sortstring(string):
    return ''.join(sorted(string))

def simplify(all_strings):
    possible_strings = defaultdict(list)
    for string in all_strings:
        possible_strings[sortstring(string).strip()].append(string)
    return possible_strings

def generate(database, length,curstring="", curdata=set()):
    if len(curstring.replace(" ", "")) > length:
        return set()
    if len((curstring).replace(" ", "")) == length:
        return curdata.union(set([curstring]))
    for i in database:
        if len((curstring+i).replace(" ", "")) <= length:
            curdata = curdata.union(generate(database.difference(set([i])),
                length, curstring+" "+i, curdata))
            database = database.difference(set([i]))
    return curdata

def analyse(database, input_string):
    cletters = countstring(input_string)
    strings = simplify(generate(database, cletters))
    data = list()
    sorted_string = sortstring(input_string).strip()
    if sorted_string in strings.keys():
        data = strings[sorted_string]
    return len(strings.values()), data

def countstring(string):
    a = countletters(string)
    return sum(a.values())

def countletters(string):
    result = {}
    for i in ascii_lowercase:
        result[i] = string.count(i)
    return result

任何人都可以提出改进方法吗？尽管我认为应该完全放弃我使用的算法，因为它的速度太慢，复杂性似乎太高了。以防万一:该程序应该足够高效以支持数万个单词和最多数十个字符的字符串的词典。这比我所做的要好得多。

Answer 1

我自己解决了部分问题。解决了生成器代码中的 for-if 反模式:

def generate(database, length,letters,curstring="",curdata=set()):
if len(curstring.replace(" ",""))>length:
    return set()
if len((curstring).replace(" ",""))==length:
    return curdata.union(set([curstring]))
t=countletters(curstring)
for i in ascii_lowercase:
    if t[i]>letters[i]:
        return set()
for i in database:
    t=countletters(curstring+i)
    test=0
    for j in ascii_lowercase:
        if t[j]>letters[j]:
            test=1
    if test: continue
    if sum(t.values())<=length:
        curdata=curdata.union(generate(database.difference(set([i])),length,letters,curstring+" "+i,curdata))
        database=database.difference(set([i]))
return curdata

现在快了很多，但如果字典包含数万个单词和/或输入字符串很长，速度仍然很慢。