由於遞歸

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.