我正在嘗試在線性時間內搜索字串中最長的子字串。如何在不使用 max 函式的情況下執行此操作？
這是問題：
給定一個字串，找出沒有重復字符的最長子字串的長度。你能在線性時間內找到解決方案嗎？
這是我的解決方案：
class Solution:
def lengthOfLongestSubstring(self, sentence):
evid = []
word = ''
for i in sentence:
if i not in word:
word = i
else:
evid.append(word)
word = ''
word = i
return len(max(evid, key=len))
print(Solution().lengthOfLongestSubstring('abrkaabcdefghijjxxx'))
謝謝！
uj5u.com熱心網友回復：
在進行成員資格測驗 ( O(N))時，您不應該對字串進行操作。一個真正的線性解決方案將使用一個set和兩個指標：
class Solution:
def lengthOfLongestSubstring(self, sentence):
crnt = set()
m = lo = hi = 0
while hi < len(s):
if (c := s[hi]) in crnt: # membership check is O(1)
# move lo past the most recent occurrence of c
while (d := s[lo]) != c:
# removing all characters along the way
crnt.remove(d)
lo = 1
lo = 1
else:
crnt.add(c)
if len(crnt) > m:
m = len(crnt)
hi = 1
return m
由于每個索引/字符crnt最多被添加到集合中或從集合中洗掉一次，兩個操作和包含檢查都為O(1)，因此這種方法是線性的。
uj5u.com熱心網友回復：
使用sliding window和避免max按照 OP 要求使用的想法相同。試試這個看看是否有幫助？
def lengthOfLongestSubstring(self, s: str) -> int:
maxSubLen = 0
start = 0
seen = {}
for i in range(len(s)):
c = s[i]
if c in seen and start <= seen[c]:
start = seen[c] 1
else:
if maxSubLen > (i-start 1):
maxSubLen = maxSubLen
else:
maxSubLen = i - start 1
#maxSubLen = max(maxSubLen, i - start 1) # no max!
seen[c] = i
return maxSubLen
轉載請註明出處，本文鏈接：https://www.uj5u.com/qianduan/336996.html
上一篇：lua拆分字串并保存在lua表中