在字符串python中查找最長的唯一子字符串

Question

我正在嘗試找到不包含重複字符的字符串中最長的子字符串的年齡老問題（有大量的版本）。我不明白爲什麼我的努力工作不正常：

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

當我的輸出獲取到第二「W」，它不會遍歷所有的SUBSTR元素。我認爲我做了一些愚蠢的事情，但我不明白它是什麼，所以一些指導將不勝感激！我覺得我要踢自己的答案...

我開頭輸出：

​​

---

編輯：

我更換了與循環

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。

例如

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返回一個基於函數分組的迭代器on提供key參數，默認爲lambda x: x。相反，我們通過使用一個可變的結構，利用一些國家默認的

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

這裏發生的事情是因爲我不能重新分配一個全球性的（本來可以如果使用的是正常的功能做了更直觀的方式）在lambda中的賦值（我可以做到這一點，使用適當的函數），我只是創建了一個全局可變結構，我可以添加/刪除。關鍵（無雙關）是我只需要通過使用短路添加/刪除項目所需的元素。

max和len是相當自我解釋，以獲得通過groupby

另一個版本而不易變的全球業務結構產生的最長的名單：

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

不知道什麼是錯在你的嘗試，但它是複雜的，在：您從列表中移除元素，同時它迭代

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

：不這樣做，它給意外的結果。

不管怎樣，我的解決辦法，不知道它的直觀，但它可能是簡單&短：

• 片與越來越指數
• 每個片段的字符串，直到你達到創建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