Description
Given a string, find the length of the longest substring without repeating characters.
Examples:
Given "abcabcbb"
, the answer is "abc"
, which the length is 3.
Given "bbbbb"
, the answer is "b"
, with the length of 1.
Given "pwwkew"
, the answer is "wke"
, with the length of 3. Note that the answer must be a substring, "pwke"
is a subsequence and not a substring.
Solution
Approach 1 :
用start, end 标记当前判别的子序列的起始与终止index。
1. 若当前序列s[start: end + 1] 没有重复字符,更新Max, 并 end + 1
2. 若当前新加入的s[end]与之前的子串subs中某元素重复,则定位subs中重复元素的index, 更新start为该index + 1,并更新subs.
依此规则,每一次end后移(+1),则进行一次判断并更新。
最终Max即为所求最长无重复子串长度。
Notice:
subs = list(s[start : end + 1])
这里若直接subs = s[start : end + 1],则subs为str类型,
需要转为list类型,即将str按字母元素分隔开。
eg. “abc” -> 'a','b','c'
因为subs中即为无重复子串,则无需用set,
可直接通过判断新加入的s[end]是否在subs中,来判断是否有重复字符
class Solution:
def lengthOfLongestSubstring(self, s):
"""
:type s: str
:rtype: int
""" if not s: return 0
start, end, Max = 0, 0, 0
subs = []
while end < len(s):
if s[end] not in subs:
subs.append(s[end])
else:
start += subs.index(s[end]) + 1
subs = list(s[start : end + 1])
Max = end - start + 1 if end - start + 1 > Max else Max
end += 1
return Max
Beats:35.65%
Runtime: 124ms
Approach 2:
基本思路与上面一致
class Solution:
def lengthOfLongestSubstring(self, s):
"""
:type s: str
:rtype: int
""" if not s:
return 0
longestlength = 1
substr = ""
for item in s:
if item not in substr:
substr += item
else:
if len(substr) > longestlength:
longestlength = len(substr) #将重复字符加入substr
substr += item
# 应该从substr中第一次出现重复字符的下一个字符开始继续判断
substr = substr[substr.index(item) + 1:] if len(substr) > longestlength:
longestlength = len(substr)
return longestlength
Beats: 44.09%
Runtime: 108ms
Approach 3: 用dict来存储判断重复元素
这里复制了leetcode上最快的答案。
解法中用到了
d: dict
i: 字母元素 d[i]: 更新后的字母元素在s中的index
每当遍历新的s元素,更新该元素在d中的映射值 (新元素:添加;已有元素:更新)
这样可以直接定位到其index, 而不需要每次通过s.index()查找
index表示当前遍历到的s中元素的ind
start表示当前子串的起始ind
count表示当前子串的长度
class Solution:
def lengthOfLongestSubstring(self, s):
"""
:type s: str
:rtype: int
""" d = {}
maxlength = 0
count = 0
start = 0
for index, i in enumerate(s):
if i in d and d[i] >= start:
count = index - d[i]
start = d[i]
else:
count+=1
d[i] = index
if count>maxlength:
maxlength = count return maxlength
Beats: 99.93%
Runtime: 68ms