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

Question

我需要制作一个程序，将带有字典和任意字符串的文件作为输入，然后输出该字典中构成给定字符串的字谜词的所有单词组合。例如，使用英语中 100 个最流行的单词和字符串"i not work"，我应该得到类似 的结果[' on it work', ' into work', ' not i work', ' know or it', ' work it no', ' to work in']，我就是这么做的。

问题是我的程序效率太低：字典中有 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

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