文字列pythonで最も長い一意の部分文字列を見つけよう

Question

私は繰り返し文字を含まない文字列の最長部分文字列を見つけるという年齢の古い質問（バージョンが多数あります）を試しています。私の試みが正常に動作しない理由を私はうまくいかないことができます。私の出力が第二「W」になると

def findLongest(inputStr): 
    resultSet = [] 
    substr = [] 

    for c in inputStr: 
     print ("c: ", c) 
     if substr == []: 
      substr.append([c]) 
      continue 

     print(substr) 
     for str in substr: 
      print ("c: ",c," - str: ",str,"\n") 
      if c in str: 
       resultSet.append(str) 
       substr.remove(str) 
      else: 
       str.append(c) 
     substr.append([c]) 



    print("Result set:") 
    print(resultSet) 
    return max(resultSet, key=len) 

print (findLongest("pwwkewambb")) 

、それはすべてのsubstr要素を反復しません。私は何か愚かなことをしたと思うが、私はそれが何であるかを見ることができないので、いくつかの指導は認められるだろう！私は答えに自分自身をキックするつもりのように私は私の出力の先頭

...感じる：

​​

---

EDIT：

私はのためのループを置き換えます

for idx, str in enumerate(substr): 
    print ("c: ",c," - str: ",str,"\n") 
    if c in str: 
     resultSet.append(str) 
     substr[idx] = [] 
    else: 
     str.append(c) 

正しい結果が得られます。唯一のことは、空の要素配列が次の文字で設定されることです。それは少し意味がないようです。より良い方法が必要です。

私の期待される出力はkewambです。

それを反復しながら、あなたはリストから要素を削除している

for str in substr: 
     print ("c: ",c," - str: ",str,"\n") 
     if c in str: 
      resultSet.append(str) 
      substr.remove(str) 

：あなたの試みで、間違っているが、それは、複雑だと何

c: p 
c: w 
[['p']] 
c: w - str: ['p'] 

c: w 
[['p', 'w'], ['w']] 
c: w - str: ['p', 'w'] 

c: w - str: ['w'] 

c: k 
[[], [], ['w']] 
c: k - str: [] 

c: k - str: [] 

c: k - str: ['w'] 

c: e 
[['k'], ['k'], ['w', 'k'], ['k']] 
c: e - str: ['k'] 

c: e - str: ['k'] 

c: e - str: ['w', 'k'] 

c: e - str: ['k'] 
... 

Answer 1

from itertools import groupby 

s = set() ## for mutable access 

''.join(max((list(g) for _, g in groupby('pwwkewambb', key=lambda x: not ((s and x == s.pop()) or s.add(x)))), key=len)) 
'kewamb' 

groupbyは、functiに基づいてグループ化されたイテレータを返します。デフォルトでlambda x: xであるkey引数で提供されます。

lambda x: not ((s and x == s.pop()) or s.add(x)) 

私は地球を再割り当てすることはできませんので、何ここで起こっていることである代わりに、私たちは、変更可能な構造を使用して、いくつかの状態を利用しているデフォルトの（通常の機能を使用している場合これは、より直感的な方法で行われている可能性）ラムダでの代入（これは正しい関数を使ってやり直すことができます）、追加/削除できるグローバルな変更可能な構造を作成しました。キー（無言）は、私が必要とする要素を追加/削除するために短絡を使うだけで、必要な要素だけを保持するということです。

def longest(x): 
    if hasattr(longest, 'last'): 
     result = not (longest.last == x) 
     longest.last = x 
     return result 
    longest.last = x 
    return True 


''.join(max((list(g) for _, g in groupby('pwwkewambb', key=longest)), key=len)) 
'kewamb' 

Answer 2

わからないことを実行しない、それができます予期せぬ結果。とにかく

、私の解決策ではなく、それは直感的だが、それはおそらく短い&簡単ですしてください：スライスごとに増加指数

と

• スライスの文字列を、あなたが到達するまでsetや店舗の手紙を作成します文字列の最後または文字はすでにsetにあります。あなたのインデックスの最大長
• は反復ごと&店のために、この長さの最大値を計算され、対応する文字列

コード：

def findLongest(s): 
    maxlen = 0 
    longest = "" 
    for i in range(0,len(s)): 
     subs = s[i:] 
     chars = set() 
     for j,c in enumerate(subs): 
      if c in chars: 
       break 
      else: 
       chars.add(c) 
     else: 
      # add 1 when end of string is reached (no break) 
      # handles the case where the longest string is at the end 
      j+=1 
     if j>maxlen: 
      maxlen=j 
      longest=s[i:i+j] 
    return longest 

print(findLongest("pwwkewambb")) 

結果：

kewamb