由于递归，hackerrank密码破解程序超时

Question

This problem简单来说就是这样：给定一组字符串和一个目标字符串，给定字符串中的所有组合可以组合在一起，形成目标字符串，有重复也无重复。在

例如

字符串：我们做我们必须做的，因为我们可以

目标：我们必须做到这一点

输出：我们做我们必须做的，因为我们可以

我采取的方法是从目标中删除每一个较长的单词，直到目标变为空。如果目标变为空，则返回输出。如果较长的单词不能解决问题，那么尝试用较短的单词，以此类推。我还使用记忆化来确保如果目标已经被试过了，那么就返回，就像回溯一样。在

这个方法通过了所有的测试用例，除了2个，我得到了超时。在

def recursions(word_map, paswd, output, remember):
    flag = 0
    if len(paswd) == 0:
        return 1
    if paswd in remember:
        return flag
    for char in paswd:
        for word in (word_map[char] if char in word_map else []):
            if paswd.startswith(word):
                output.append(word + " ")
                if recursions(word_map, paswd[len(word):], output, remember):
                    return 1
                output.pop()
        remember[paswd] = 1
    return flag

请帮助提供提示。完全解是here。在

Answer 1

你可以尝试动态编程的方法，你可以标记每个密码的结束位置。首先在较长字符串的开头尝试每个密码。如果合适，在较长的字符串中标出结束位置。然后，您可以对较长字符串中的每个位置重复相同的过程，其中前一个位置被标记为结束位置。在

希望这有助于你开始，我故意遗漏了一些完整解决方案所需的信息，所以如果你仍然无法解决，请在评论中告诉我。在

编辑下面是一个关于我所说内容的简短示例。它不允许您重建解决方案，但它展示了如何在不使用递归的情况下进行匹配：

passwords = ['foo', 'bar']
login = 'foobar'

ends_here = [False] * len(login)

for i in range(len(ends_here)):

    # Match password at the beginning or if password match
    # ended to previous index
    if i == 0 or ends_here[i - 1]:
        for pw in passwords:
            if login.find(pw, i, i + len(pw)) != -1:
                ends_here[i + len(pw) - 1] = True

print(ends_here)
print('We can match whole login attempt:', ends_here[-1])

输出：

^{pr2}$

编辑仔细查看问题中提供的代码。问题出在匹配字符串被目标中包含的字符过滤的行：for char in paswd:。不是对目标字符串中的每个字符进行筛选，而是对每个唯一的字符进行筛选：for char in set(paswd):。解决这个问题，解决方案运行得更快，但如果根本没有这种过滤，可能会更快，因为最短的字符串数是10。在