站点图标 Wankko Ree's Blog

[刷题]LeetCode 3. 无重复字符的最长子串

代码git:History for 3. 无重复字符的最长子串.py - WankkoRee/LeetCodeAnswersWithPython3

这题刚开始想错了,所以前两个提交的版本都是不正确的思路。

刚开始我以为只要出现重复,那就找上一次这个字符的出现位置然后求个差值就是这次的字串长度,比如说abcabcbb,刚开始找到的重复是开头的abca的俩个a,那么长度就是3-0=3,然后bcab4-1=3cabc5-2=3bcb6-4=2,所以取最大就是3

然后就按这思路写了一下。

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        a = {_: -1 for _ in "abcdefghijklmnopqrstuvwxyz"}
        m = 0
        for i, x in enumerate(s):
            if a[x] == -1:
                a[x] = i
            else:
                m = max(m, i - a[x])
                a[x] = i
        if m:
            return m
        else:
            return len(s)

solution = Solution()
assert solution.lengthOfLongestSubstring("abcabcbb") == 3
assert solution.lengthOfLongestSubstring("bbbbb") == 1
assert solution.lengthOfLongestSubstring("pwwkew") == 3
assert solution.lengthOfLongestSubstring("") == 0

发现有些数据报错了,仔细看了下题目,原来字符范围不只是字母,于是修了一下。

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        a = {}
        m = 0
        for i, x in enumerate(s):
            if x not in a.keys():
                a[x] = i
            else:
                m = max(m, i - a[x])
                a[x] = i
        if m:
            return m
        else:
            return len(s)

solution = Solution()
assert solution.lengthOfLongestSubstring("abcabcbb") == 3
assert solution.lengthOfLongestSubstring("bbbbb") == 1
assert solution.lengthOfLongestSubstring("pwwkew") == 3
assert solution.lengthOfLongestSubstring("") == 0

然后就莫名其妙地在aab上报错了,于是就调试跟了下数据看看啥情况,结果发现之前的思路不完全对,因为可能存在abcba这种情况,而我的代码因为是往前找当前字符的,所以这种情况也会被认为是合理的,但实际上并不合理...再比如说题目这种aab的,第一回找到了个aa算出来长度1,但是最后本来应该算进来的字串ab却并不被我的代码认可,所以感觉是方向错了。

于是就重新构思一下,刚才的那个直觉应该没错,肯定是要找前后重复的然后进行最大判断,但是并不能简单地往前找,所以就搞个左右下标来记录之前找到的子串s[l:r]吧。

如果在之前的子串里找到了当前字符,那么就把这个子串的长度记一下,也就是r-l,然后把左下标改成子串中当前字符的位置的后一个,比如说以第一个样例为例,之前字串是s[l:r] = s[0:3] = 'abc',然后当前字符是s[3] = 'a',所以就找到了s[0] = 'a',那么就把子串更新一下,变成s[1:4] = 'bca',也就是把左下标变成0+1,这里的0s[0] = 'a'0

那么大致写一下代码然后调试一下修修bug。

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        l = 0
        r = 0
        m = 0
        for i, x in enumerate(s):
            p = s[l:r].find(x)
            if p != -1:
                m = max(m, r-l)
                l += p+1
            r = i + 1
        m = max(m, r - l)
        return m

solution = Solution()
assert solution.lengthOfLongestSubstring("abcabcbb") == 3
assert solution.lengthOfLongestSubstring("bbbbb") == 1
assert solution.lengthOfLongestSubstring("pwwkew") == 3
assert solution.lengthOfLongestSubstring("") == 0

assert solution.lengthOfLongestSubstring("aab") == 2

成功a掉测试数据。

执行用时: 56 ms , 在所有 Python3 提交中击败了 77.65% 的用户
内存消耗: 15 MB , 在所有 Python3 提交中击败了 66.36% 的用户
通过测试用例: 987 / 987


The End
退出移动版