誤解題意的解法 又適用於 Description 的各Example
錯誤示範#1
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
max = 0
#length = 1
print(len(s))
for i in range(len(s)):
length = 1
print("i"+s[i])
for j in range(i+1,len(s)):
if s[i]==s[j]:
print("repeat"+str(j)+" "+s[j])
print("max:"+str(max))
if length>max:
max = length
break
else:
length = length+1
print("len"+str(length))
#if length>max:
#print(str(length))
#max = length
print("Ans:"+str(max))
if len(s)==1:
return 1
elif (len(s)!=0) and (max==0):
return len(s)
return max
看了別人思路,懂了這題的 substring 的意思。
紀錄之前有出現的字母,後續如果有出現則ignore?
錯誤示範#2
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
ans = set()
for i in range(len(s)):
ans.add(s[i])
print(len(ans))
return len(ans)
正解
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
ans = set()
left,right = 0,0
res = 0
#for i in range(len(s)):
while left < len(s) and right < len(s):
if s[left] in ans and s[right] in ans:
ans.remove(s[left])
#left = right
left = left + 1
else:
ans.add(s[right])
right = right + 1
res = max(res,len(ans))
#ans.add(s[])
print(ans)
return res
Reference: https://blog.csdn.net/fuxuemingzhu/article/details/82022530
正解思路 內化
sol : 雙指標 left,right
都往右移
left 往右移的時機點是 s[right] 和 s[left] 都在set 裡,也就是碰到重複的字母。
而 right 往右移時機點是 目前位置指向的字母不在 set 裡,同時 set add 不曾出現的字母,
並且 更新最長子字串的長度: 目前記錄 vs 歷史紀錄 取 max。
note : Python set 存 無序不重複元素