leetcode_3

Posted on | In

[LeetCode: No.3]

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.
解法一

粗暴的想法是利用循环嵌套对所有情况进行遍历。大体的思路是：第一层循环从字符串的最左侧到左右侧第二个，然后第二层循环从第一层紧跟着的一个到最后的字符串，之后比较长度得到最大长度的子字符串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        max_len = 0 #用这个值记录我们要返回的最长子字符串长度
        #当原字符串长度为0或1的特殊情况
        if (len(s) == 1 or len(s) == 0):
            max_len = len(s)
        #开始遍历每一个子字符串，并进行长度比较，得到最长的那个
        for i in range(0,len(s)-1):
            for j in range(i+1, len(s)):
                if s[j] in s[i:j]:
                    if j-i > max_len:
                        max_len = j - i
                    break
                elif j == len(s) - 1:  	
				#当j是最后一个字符时，需要加上一个单位
                    if max_len < j - i + 1:
                        max_len = j - i + 1
        return max_len

这种解法虽然可以通过，但是效率很低，时间会很长

解法二
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        #创建一个空字典，其存放的形式是“单字符:出现位置的索引”
        indexDict = {}
        #存放记录最大长度和当前循环下的长度
        maxLength = currMax = 0
        for i in range(len(s)):
            #这里是当s[i]没有在之前出现过，则当前长度currMax自动加一
            #当出现了重复字符，则比较当前找到的子字符串长度和历史最大长度
            #重点是这里i - indexDict[s[i]] - 1 的含义；代码后举例具体讲解
            if s[i] in indexDict and i - indexDict[s[i]] - 1 <= currMax:
                if maxLength < currMax:
                    maxLength = currMax
                currMax = i - indexDict[s[i]] - 1
            currMax = currMax + 1                
            indexDict[s[i]] = i     #这一步也非常关键，可以更新重复字符的位置
        return maxLength if currMax < maxLength else currMax

接下来举例说明下为什么【i - indexDict[s[i]] - 1】代表了当前找到子字符串的长度。 比如字符串’abcdadd’，代码运行过程中一直迭代到i=3【对应字符d】时，都不满足s[i] in indexDict ,不执行条件语句，而是currMax依次加一，并且将字符信息以{s[i]:i}的形式存放在字典中。当继续迭代i=4时，进入条件语句，这里主要解释【i - indexDict[s[i]] - 1】，检测到了重复字符’a’，之前该字符出现位置为i=0处即【indexDict[s[i]] =0】这时候当前检测到的无重复字符子串为’abcd’，长度为【4-indexDict[s[i]] -1 = 3】。其他同此例。