专栏首页用户6811391的专栏Python 版 LeetCode 刷题笔记 #3 无重复字符的最长子串

Python 版 LeetCode 刷题笔记 #3 无重复字符的最长子串

今天这题目乍一看,在字符串中找来遍历即可,但实际操作下来,还是有些复杂的,也配得上其中等难度的定位了。

题目

中文题目

第 3 题 无重复字符的最长子串:

给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。

示例:

输入: "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。

输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b",所以其长度为 1。

输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3。
     请注意,你的答案必须是 子串 的长度,"pwke" 是一个子序列,不是子串。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/longest-substring-without-repeating-characters

英文题目

Question 3 Longest Substring Without Repeating Characters: Given a string, find the length of the longest substring without repeating characters. Example:

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

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

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.

思路

以 "abcabcbb" 为例,最初我的思路是检测重复字母的出现,比如当字母 "a" 第二次出现时,就把 "abc" 分离出去作为第一个子串,然后继续分离出 "abc"、"b" 和 "b"。以此思路完成代码提交后,遇到个问题:面对 "dvdf" 字符串,我们得到的子串是 "dv" 和 "df" 两个长度为 2 的子串。但是,"vdf" 是符合条件的长度为 3 的子串,也就是说,我们刚刚的思路漏掉了很多子串情况,是需要我们遍历字符串中每个字符作为子串起点来考虑的。

那么我们按最基础的遍历来看,对字符串中每个字符,以其为起点,对后续能产生的子串进行检测,当出现重复字符时即可停止,得到子串长度并记录。这样经过一圈遍历,获得每个字符为起点的所有最长子串长度,取最大值得到结果。

代码

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        # temp 用来作为保存未重复字符的子串字符列表
        temp =[]
        # 返回的结果默认有个 0 ,因为最终测试时也会出现对 "" 空字符串处理的情况
        result=[0]
        # 对字符串进行遍历
        for i,item in enumerate(s):
            # 以被遍历的该字符为起点,遍历其后的各字符以组成子串
            for j,body in enumerate(s[i:]):
                # 如果重复出现字符
                if body in temp:
                    # 将子串的长度保存到结果列表中
                    result.append(len(temp))
                    # 该子串可以被清空继续检测新的子串
                    temp=[]
                    # 通过 break 跳出对后续字符的遍历,开启新的 for i 的循环
                    break
                else:
                    # 如果没有出现重复字符,将新出现的字符添加到子串字符列表中
                    temp.append(body)
                # 如果一直到最后一位都没有出现重复字符,将最后子串长度记录到结果中
                if j==len(s[i:])-1:
                    result.append(len(temp))
                    temp=[]
        # 返回结果列表中的最大值
        return max(result)

提交答案

这次提交答案后,看到测评结果简直要哭出来了:

中文区结果:

执行用时 :4408 ms, 在所有 Python3 提交中击败了5.00%的用户 内存消耗 :13.8 MB, 在所有 Python3 提交中击败了5.05%的用户

英文版结果:

Runtime: 4332 ms, faster than 5.01% of Python3 online submissions for Longest Substring Without Repeating Characters. Memory Usage: 14.4 MB, less than 5.10% of Python3 online submissions for Longest Substring Without Repeating Characters.

运行时间和内存消耗都不好看,啥也不说了,优化吧。

优化

简单的微调可以考虑把获取长度最大值的步骤修改下,现在是把所有子串长度存成列表取最大值,完全可以改成只用一个变量通过比较保存最大值。但试了下提升的并不多,可见问题关键还是在这两个嵌套的 for 循环上。

参考了推荐答案的思路,在我们对字符串遍历时,例如 "abcabcbb" 我们从最开始的 "a" 开始找子串,当检测到第 4 位 "a" 时,这是出现相同字符了,这时我们不再清空子串,而是将子串最初位置的 "a" 剔除从而得到 "bca",这样便可以通过一次遍历实现我们之前两层 for 嵌套的效果了!

代码实现

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:        
        # 存放子串长度的结果列表
        result = []
        # 存放子串字符的列表
        temp=[]
        # 对输入字符串进行遍历
        for item in s:
            # 如果字符重复
            if item in temp:
                # 将子串长度添加到结果列表中
                result.append(len(temp))
                # 记录目前子串的初始位置
                start_index = temp.index(item)
                # 将子串初始位置右移一位、剔除重复的第一位,重新赋值给子串
                temp=temp[start_index+1:]
            # 无论是否字符重复,将该字符添加到子串列表中(重复时上一步已经剔除了)
            temp.append(item)
        # 将最后的子串长度记录
        result.append(len(temp))
        # 返回最长的子串
        return max(result)

表现结果:

Runtime: 64 ms, faster than 60.88% of Python3 online submissions for Longest Substring Without Repeating Characters. Memory Usage: 14.1 MB, less than 5.10% of Python3 online submissions for Longest Substring Without Repeating Characters.

我惊呆了。。运行时间从 4332 ms 降到了 48ms !这是近百倍的提升么?又翻了些其它答案之后,还潜在的提升点在于目前我们是通过一个列表存储子串字符来实现的,这个可以通过记录起始两个位置坐标的变量来取代,但可能比较绕,就没有继续探究了。

结论

第三题,依然是中等难度,乍一看没这么难,但实际考虑时测试用的字符串还是存在各种情况的,提交时报错不断试错完善。同时,优化中提到的思路也是避开暴力穷举的算法设计,讨论区也称呼这种方法为“滑动窗口”解法,确实是很有启发。

现在接触这种有难度的算法题比较少,有些地方还挺费时间的,希望多多练习可以提高效率吧,明天继续~

本文分享自微信公众号 - TTTEED(TEDxPY),作者:TED

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-04-11

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 罗马数字背后的秘密——LeetCode XII XIII 题记

    印象中的罗马数字,多出现在文档标题或序号中:I、II、III、IV、V、VI 等。它是阿拉伯数字传入之前使用的一种数码。其采用七个罗马字母作数字:Ⅰ(1)、X(...

    TTTEED
  • 模拟除法与匹配单词—— LeetCode 第 29、30 题记

    今天遇到的是一道不用除号来实现除法运算的中等难度的题,和一道在字符串中检测匹配特定词语的困难级别的题。然而中等难度的,花费两个多小时才完成,困难的这道半个多小时...

    TTTEED
  • Python print 玩转“点阵字”

    学习python3第一句大概率是 print(“hello world”) 吧?既然可以逐行逐个地输出字符,那么把字符组成汉字应该也不难吧?经过一番搜索与尝试,...

    TTTEED
  • 几行Python代码打造自己的磁盘垃圾文件清理器

    本文假设某些特定类型的文件和大小为0的文件为垃圾文件,可以自由扩展代码的列表,也就是垃圾文件的类型。 from os.path import isdir, j...

    Python小屋屋主
  • 树的遍历非递归实现

    ShenduCC
  • Leetcode-Easy 985. Sum of Even Numbers After Queries

    We have an array A of integers, and an array queries of queries.

    致Great
  • Spring中AOP面向切面编程的概念到底是什么?

    1.AOP(面向切面的编程) 每当执行某个方法时,按照配置文件,在它前或后,执行另外一段程序,就像切了一刀一样。aop的概念有点儿像filter。但过滤器只能切...

    马克java社区
  • [每日一题]最少划分子串

    给定一个包含n个小写字母的字符串s,要求将字符串划分成若干个连续子串,子串中的字母类型相同,同时子串的字母个数不超过k,输出最少划分的子串数量。

    呼延十
  • 【AI白身境】搞计算机视觉必备的OpenCV入门基础

    它是一款由Intel公司俄罗斯团队发起并参与和维护的一个计算机视觉处理开源软件库。

    用户1508658
  • python 外部命令执行--OS

     Python 也可以通过os、subprocess执行外部shell命令对POSIX类型系统进行操作。

    py3study

扫码关注云+社区

领取腾讯云代金券