題目: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:
def lengthOfLongestSubstring(self, s: str) -> int:
max = 0
res = list(s)
for x in range(len(res)):
n = 1
dict = {}
dict[res[x]] = 1
for y in range(x+1, len(res)):
if res[y] in dict:
break
else:
dict[res[y]] = 1
n = n+1
if n > max:
max = n
return max
耗時504ms
解法二:用标記位記錄起始位置,一旦出現重複位(如第2、5位上出現的字元重複),則将起始位記為第一次記錄位置(第2位)的下一位
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
start = 0
dict={}
max = 0
for i in range(len(s)):
if s[i] not in dict:
dict[s[i]] = i
else:
if dict[s[i]] + 1 > start:
start = dict[s[i]] + 1
dict[s[i]] = i
if i - start + 1 > max:
max = i - start + 1
return max
耗時64ms