[leetcode]3.无重复字符的最长子串
2019-01-09 本文已影响0人
LeeYunFeng
题目描述:
给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。
- 示例 1:
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。 - 示例 2:
输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b",所以其长度为 1。 - 示例 3:
输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3。
请注意,你的答案必须是 子串 的长度,"pwke" 是一个子序列,不是子串。
解题思路:
-
最初的思路是采用笨办法,也就是暴力的列出所有子串,判断各个子串是否满足“不含重复字符”的条件,如果满足则记录字符串长度。从最长的子串开始搜索,一旦出现满足条件的子串,就返回结果。
采用以上方法的时间复杂度为O(n^3),最终在某些测试样例上运行超时。 -
借鉴其它的思路,可以只遍历一次字符串的各个字符,记录当前最长子串的长度,同时记录当前子串的起始位置,遍历完成后即可得最终结果。使用这种方法时,不仅要用到各个字符的value,还需要用到对应的index,充分用到所有相关信息。时间复杂度为O(n)。
笨办法:
class Solution(object):
def lengthOfLongestSubstring(self, s):
"""
:type s: str
:rtype: int
"""
n=len(s)
if n==0:
return 0
for l in range(n,0,-1):
for i in range(0,n-l+1,1):
d={}
for j in s[i:i+l]:
if d.get(j):
d[j]+=1
else:
d[j]=1
if max(d.values())==1:
return l
更快速的方法:
class Solution(object):
def lengthOfLongestSubstring(self, s):
"""
:type s: str
:rtype: int
"""
start=0#当前子串的起始位置
lmax=0#当前最大的子串长度
d={}#用于记录value和index之间的映射
for i,v in enumerate(s):
# v in d表示此前出现过相同的字符,需要重新指定start
if v in d:
start=max(d[v]+1,start)
# 记录当前各个字符对应的最大index
d[v]=i
# 得到当前最大的子串长度
lmax=max(lmax,i-start+1)
return lmax