由于递归

Question

This problem只是重申hackerrank密码破解超时是这样的：给定一串字符串和目标字符串，什么从给定字符串的所有组合可以结合在一起，以形成目标字符串和不重复的。

例如

串：我们做什么，我们一定要，因为我们可以

目标：wedowhatwemustbecausewecan

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

方法我带是从目标中删除每个更长的单词，直到目标变为空。如果目标变为空，那么只需返回输出。如果更长的单词不会导致解决方案，那么尝试使用更短的单词等。我也使用memoization来确保如果目标已经尝试过，那么只需返回，就像使用memoization进行回溯一样。

这apporach通过了所有的测试用例，除了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]) 

输出：

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

编辑注意到在提供的代码细看题。问题出现在匹配字符串被目标中包含的字符过滤的行上：for char in paswd:。而不是做滤波在目标字符串中的每个字符过滤应该为每个独特字符来完成：for char in set(paswd):。解决方案和解决方案的运行速度要快得多，但如果根本没有那种过滤功能，那么速度可能会更快，因为最大数量的较短的字符串是10.