问题描述:
给定一个字符串,找出不含有重复字符的最长子串的长度。
示例 1:
输入: "abcabcbb"
输出: 3
解释: 无重复字符的最长子串是"abc",其
长度为 3。
示例 2:
输入: "bbbbb"
输出: 1
解释: 无重复字符的最长子串是"b"
,其长度为 1。
示例 3:
输入: "pwwkew"
输出: 3
解释: 无重复字符的最长子串是"wke"
,其长度为 3。
请注意,答案必须是一个子串,"pwke"
是一个子序列 而不是子串。
学业繁重,没时间写了。。。。。。
方法1:s="pwwkew" d={} ({"p":0,"w":1,"w":2,"k":3,"e":4,"w":5}) ,当s[i]在d中,start=d[s[i]] + 1从下一个位置开始,temp 存储最大长度 temp=max(i-start+1,temp)
class Solution:
def lengthOfLongestSubstring(self, s):
"""
:type s: str
:rtype: int
"""
d={}
start = 0
temp = 0
for i in range(len(s)):
if s[i] in d and start <= d[s[i]]:
start = d[s[i]] + 1
temp = max(temp,i-start+1)
d[s[i]] = i
return temp
方法2:
class Solution:
def lengthOfLongestSubstring(self, s):
"""
:type s: str
:rtype: int
"""
sub=''
sub_len=0
max_len=0
max_sub=''
for letter in s:
if letter in sub:
if sub_len>max_len:
max_len=sub_len
max_sub=sub
index=sub.index(letter)
sub=sub[index+1:]+letter
sub_len=sub_len-index
else:
sub=sub+letter
sub_len+=1
if sub_len>max_len:
max_len=sub_len
return max_len
方法3:
class Solution:
def lengthOfLongestSubstring(self, s):
"""
:type s: str
:rtype: int
"""
start = max_len = 0
used = {} for i in range(len(s)):
if s[i] in used and start <= used[s[i]]:
start = used[s[i]] + 1
else:
max_len = max(max_len, i - start + 1)
used[s[i]] = i return max_len
2018-10-15 22:43:21