再帰によるハッカークランクパスワードクラッカーのタイムアウト

Question

This problemこれは単純に言い換えれば、与えられた文字列からなるすべての組み合わせが結合して繰り返しの有無にかかわらずターゲット文字列を形成することができます。

文字列：私たちは、私たちがしなければならないん我々は

ターゲットことができるので：

wedowhatwemustbecausewecan出力を：我々は、我々は私が撮った

アプローチをしていることができなければならないので、何をすべきかターゲットが空になるまでターゲットから長い単語をすべて削除します。ターゲットが空になると、出力が返されます。長い単語が解決策につながっていない場合は、短い単語などで試してください。私はまた、ターゲットが既に試されている場合には、memoizationを使ってバックトラッキングと同じように戻ってくることを確認するためにメモを使用しています。

このアプリケーションは、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:。ターゲット文字列のすべての文字に対してフィルタリングを行う代わりに、ユニーク文字ごとにフィルタリングを実行する必要があります。for char in set(paswd):。この問題を解決するには、はるかに高速ですが、短い文字列の最大数が10であるため、この種のフィルタリングがまったく行われない場合はさらに高速になります。