連結:
https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/
題目:
給定一個字元串,請你找出其中不含有重複字元的 最長子串 的長度。示例 1:
輸入: “abcabcbb” 輸出: 3 解釋: 因為無重複字元的最長子串是 “abc”,是以其長度為 3。
示例 2:
輸入: “bbbbb” 輸出: 1 解釋: 因為無重複字元的最長子串是 “b”,是以其長度為 1。
示例 3:
輸入: “pwwkew” 輸出: 3 解釋: 因為無重複字元的最長子串是 “wke”,是以其長度為 3。
請注意,你的答案必須是 子串 的長度,“pwke” 是一個子序列,不是子串。
我的解法:
class Solution(object):
def lengthOfLongestSubstring(self, s):
if not s:
return 0
l ,i, n = 1, 1, 1
dic = {s[0]:0}
while i < len(s):
if s[i] not in dic:
dic[s[i]] = i
n += 1
i += 1
else:
l = max(l, n)
i = dic[s[i]] + 2
dic = {s[i-1]:i-1}
n = 1
l = max(l, n)
return l
優化:用start标記,就不用總更新dict
class Solution(object):
def lengthOfLongestSubstring(self, s):
hash={}
start=0
max_length=0
for i,string in enumerate(s):
if string in hash and start<=hash[string]:
start=hash[string]+1
else:
max_length=max(max_length,i-start+1)
hash[string]=i
return max_length