欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Longest Substring Without Repeating Characters (leetcode 3)

程序员文章站 2022-07-13 21:29:48
...

version 1:

本问题是寻找最长的子串,且子串无重复字符,且注意是子串不是子序列。简单粗暴的用直觉想了个时间复杂度为Longest Substring Without Repeating Characters (leetcode 3)的方法,简单粗暴的办法,先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

Longest Substring Without Repeating Characters (leetcode 3)

version 2:

第一个版本的方法虽然思想简单,但耗时太长,所以经过一番冥思苦想,采用滑动窗口的方法,将两层循环变成一层循环。使用两个定位的变量begin 和 end,end随着循环遍历不断的往后游走,对当前处理的字符,检查是否出现在begin 到 end之间,如果没有,end往后一位,意味着滑动窗口增大;若出现了,与历史最大滑动窗口比较,记录下最大的滑动窗口,并将start移动到重复字符的后面位置。本次算法的时间复杂度是Longest Substring Without Repeating Characters (leetcode 3)。结果时间上降低了一个量级。代码与结果如下:

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		

Longest Substring Without Repeating Characters (leetcode 3)

这暂时是笔者想到的比较好的方法,可能会有更精妙的解法,等笔者解锁新解法的时候再来更新,也欢迎交流。