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

Question

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

例如

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

目标：wedowhatwemustbecausewecan

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

我采用的方法是从目标中删除每个较长的单词，直到目标变空。如果目标变为空，则输出 return。如果较长的词没有导致解决方案，则尝试使用较短的词等。我还使用记忆来确保如果目标已经尝试过，那么只需 return，与记忆回溯相同。

这个方法通过了除 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

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

希望这能帮助您入门，我故意遗漏了完整解决方案所需的一些信息，所以如果您仍然遇到困难，请在评论中告诉我。

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

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])

输出：

[False, False, True, False, False, True]
We can match whole login attempt: True

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

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

hackerrank password cracker timeout due to recursion

python

algorithm

recursion

memoization

backtracking