小编Mas*_*lah的帖子

我需要制作一个程序，将带有字典和任意字符串的文件作为输入，然后输出该字典中构成给定字符串的字谜词的所有单词组合。例如，使用英语中 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(" …