LeetCode(Python3)3.无重复字符的最长子串

Question:

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

Example1:

Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.

Example2:

Input: s = "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.

Example3:

Input: s = "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.

Mentality:

  • 首先可以使用滑动窗口的方式,用来遍历我们的字符串;
  • 如果遇到无重复的字符,右边界不断右移,如果遇到重复的,左边窗口就缩小,直到重复的字符移除了左边界。并在这个过程中不断记录更新最大的字符长度,输出。

Code:

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        if len(s) == 0:
            return 0
        cur_len = 0
        max_len = 0
        left = 0
        lookup = set()
        for i in range(len(s)):
            cur_len += 1
            while s[i] in lookup:
                lookup.remove(s[left])
                left += 1
                cur_len -= 1
            max_len = max(max_len, cur_len)
            lookup.add(s[i])
        return max_len

 Result:

LeetCode(Python3)3.无重复字符的最长子串_第1张图片

将以上代码提交后,发现运算速度不快,于是学习了排在前列的代码,对代码进行了一波优化。


Mentality

  • 这类代码是用字典来存储每次出现过的字符以及下标,如果遇到重复的就将字符对应的下标进行更新,返回无重复最长的最长子串.

New Code:

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        res = 0
        i = -1
        lookup = {}
        for j in range(len(s)):
            if s[j] in lookup:
                if lookup[s[j]] > i:
                    i = lookup[s[j]]
            lookup[s[j]] = j
            if j - i > res:
                res = j - i
        return res

Result:

LeetCode(Python3)3.无重复字符的最长子串_第2张图片 

你可能感兴趣的