LeetCode Notes_#3 Longest Substring Without Repeating Characters

LeetCode 

Contents

题目

Given a string, find the length of the longest substring without repeating characters.

Example 1:

Input: "abcabcbb"

Output: 3

Explanation: The answer is "abc", with the length of 3.

Example 2:

Input: "bbbbb"

Output: 1

Explanation: The answer is "b", with the length of 1.

Example 3:

Input: "pwwkew"

Output: 3

Explanation: 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

思路和解答

思路

• 题目要求
  • 给出一个字符串，找到其中最长的不重复的子字符串

如果出现两个相同的长度的，且都是最长的子字符串，返回长度就可以了

• 思路
  • 先找到所有不重复的子字符串，然后从其中找出最长的一个
    • 不重复的子字符串
      • 从头到尾遍历，字符串每次增加一个字母，如果后一个字母出现在了前面的字符串中，那么从这个字母前面划分出了一个子字符串；以此类推，得到所有子字符串
    • 然后遍历得到他们的长度，取出最大值

s='abcd's[1:3]

'bc'

解答

• 错误尝试

class Solution(object):    def lengthOfLongestSubstring(self, s):        """        :type s: str        :rtype: int        """        if len(s)>1:            SubStringList=[]            tmpSubString=s[0]            tmpChar=''            for i in range(1,len(s)):#存在重复的情况                tmpChar=s[i]                if tmpChar  in  tmpSubString:#遇到重复，就开始划分                    SubStringList.append(len(tmpSubString))                    tmpSubString=tmpChar                    if i==len(s)-1:#假如到最后一个字符被划分了，那么要把他加进去                        SubStringList.append(len(tmpSubString))                else:#没有遇到重复，就继续延长字符串                    tmpSubString=tmpSubString+tmpChar                    if i==len(s)-1:                        SubStringList.append(len(tmpSubString))            if len(SubStringList)==0:#没有append说明一直都没有重复                return len(s)            else:                print SubStringList                return max(SubStringList)        else:            return len(s)

没有考虑到这种情况："dvdf"，我不能简单的去划分，所以感觉应该用两层循环，遍历以每一个字符开头的每一个子字符串

• 写了一个暴力方法，但是面对很长的输入时，超时了....emmm

class Solution(object):   def lengthOfLongestSubstring(self, s):       """       :type s: str       :rtype: int       """       if len(s)>1:           SubStringList=[]           tmpSubString=''           tmpChar=''           for i in range(0,len(s)):               for j in range(i+1,len(s)+1):                   tmpChar=s[j-1]#从第i个字符开始                   if tmpChar in tmpSubString:                       SubStringList.append(len(tmpSubString))                       tmpSubString=''                       break#遇到重复的，就直接跳出了                   else:#否则就继续遍历                       tmpSubString=s[i:j]#从i开始到j                       if j==len(s):                           SubStringList.append(len(tmpSubString))                           tmpSubString=''           return max(SubStringList)       else:           return len(s)

#没有通过的testcase就是将以下的字符串重复了几十遍....丧心病狂...在我的电脑上跑了大概3s吧....len('abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&\'()*+,-./:;<=>?@[\\]^_`{|}~ ')

95

高票解答

最后还是看了答案，思路在这里：,实在是很强....时间复杂度和空间复杂度都降低了好多...

def lengthOfLongestSubstring(self, s):            dic, res, start, = {}, 0, 0            for i, ch in enumerate(s):                if ch in dic:                    # update the res                    res = max(res, i-start)                    # here should be careful, like "abba"                    start = max(start, dic[ch]+1)                dic[ch] = i        # return should consider the last         # non-repeated substring            return max(res, len(s)-start)