3无重复字符的最长子串
程序员文章站
2022-06-10 22:26:55
...
方法一:滑动窗口
以每个字符为开头,寻找无重复字符的最长子串
class Solution(object):
def lengthOfLongestSubstring(self, s):
if not s:
return 0
start = 0
res = 0
for i in range(len(s)):
if not self.isUnique(s[start:i+1]):
start+=1
elif res < i+1-start:
res = i+1-start
return res
def isUnique(self,s):
strList = list(s)
for i in range(len(s)):
if s.count(strList[i]) != 1:
return False
return True
方法二:滑动窗口改进
实际上,没有必要寻找以每个字符开头的子串,从重复的字符开始寻找可以节约时间
class Solution(object):
def lengthOfLongestSubstring(self, s):
substr = {}
i,res = 0,0
for j in range(len(s)):
if s[j] in substr:
i = max(substr[s[j]],i)
res = max(res,j-i+1)
substr[s[j]] = j+1
return res
上一篇: LeetCode编程题总结