Longest Substring Without Repeating Characters (leetcode 3)
程序员文章站
2022-07-13 21:29:48
...
version 1:
本问题是寻找最长的子串,且子串无重复字符,且注意是子串不是子序列。简单粗暴的用直觉想了个时间复杂度为的方法,简单粗暴的办法,先work再说,但是也能发现,效率是很低的,稍后的版本再选择进行提升。简单粗暴的办法就是使用双重循环(屡试不爽哈哈):外重循环遍历整个字符串,内重循环发现以当前元素最为起始字符的最长字符串
class Solution:
def lengthOfLongestSubstring(self, s):
"""
:type s: str
:rtype: int
"""
# pick out the special case
if len(s)<1 or s == None:
return 0
# intuition lead us to do it like this
# use two loop
# the outside loop traverses all the character
# the inside loop to find the longest substring without repeating charaters
rlength = 1
length = len(s)
for i in range(0,length):
# the outside loop
for j in range(i+1,length):
# the inside loop
# if s[j] not in s[i:j](s[i...j-1],end of s[j-1])
# we can add the length of the substring which start at s[i]
# else we should deal with s[i+1]
if s[j] not in s[i:j]:
if j-i+1 > rlength:
rlength = j-i+1
else:
break
return rlength
version 2:
第一个版本的方法虽然思想简单,但耗时太长,所以经过一番冥思苦想,采用滑动窗口的方法,将两层循环变成一层循环。使用两个定位的变量begin 和 end,end随着循环遍历不断的往后游走,对当前处理的字符,检查是否出现在begin 到 end之间,如果没有,end往后一位,意味着滑动窗口增大;若出现了,与历史最大滑动窗口比较,记录下最大的滑动窗口,并将start移动到重复字符的后面位置。本次算法的时间复杂度是。结果时间上降低了一个量级。代码与结果如下:
class Solution:
def lengthOfLongestSubstring(self, s):
"""
:type s: str
:rtype: int
"""
# pick out the special case
if len(s)<1 or s == None:
return 0
begin = 0
end = 1
# begin and end is the begin and end of the sliding window
maxWin = 1
# update maxWin = end - begin
for i in range(1,len(s)):
# if the current element exist in the window s[beging:end]
# we should start the window in the later element behind the repeat element
# at the same time, update the maxWin
# whatever situation,we should add 1 to end
if s[i] in s[begin:end]:
if end - begin > maxWin:
maxWin = end - begin
begin += s[begin:end].index(s[i]) + 1
end += 1
else:
end += 1
# don't forget update the maxWin in the end
if end - begin > maxWin:
maxWin = end - begin
return maxWin
这暂时是笔者想到的比较好的方法,可能会有更精妙的解法,等笔者解锁新解法的时候再来更新,也欢迎交流。
推荐阅读
-
LeetCode - 3.Longest Substring Without Repeating Characters(388ms)
-
[LeetCode]3.Longest Substring Without Repeating Characters
-
Leetcode_3. Find the longest substring without repeating characters
-
3-Longest Substring Without Repeating Characters @LeetCode
-
Longest Substring Without Repeating Characters (leetcode 3)
-
【Leetcode 3】Longest Substring Without Repeating Characters
-
Leetcode 3 Longest Substring Without Repeating Characters
-
leetcode【3】Longest Substring Without Repeating Characters
-
LeetCode(3)Longest Substring Without Repeating Characters
-
leetcode3. Longest Substring Without Repeating Characters