前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >Python 版 LeetCode 刷题笔记 #3 无重复字符的最长子串

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

作者头像
TTTEED
发布2020-07-08 19:57:01
7040
发布2020-07-08 19:57:01
举报
文章被收录于专栏:用户6811391的专栏

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

题目

中文题目

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

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

示例:

代码语言:javascript
复制
输入: "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:

代码语言:javascript
复制
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 的子串,也就是说,我们刚刚的思路漏掉了很多子串情况,是需要我们遍历字符串中每个字符作为子串起点来考虑的。

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

代码

代码语言:javascript
复制
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 嵌套的效果了!

代码实现

代码语言:javascript
复制
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 !这是近百倍的提升么?又翻了些其它答案之后,还潜在的提升点在于目前我们是通过一个列表存储子串字符来实现的,这个可以通过记录起始两个位置坐标的变量来取代,但可能比较绕,就没有继续探究了。

结论

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

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

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2020-04-11,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 TTTEED 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 题目
    • 中文题目
      • 英文题目
      • 思路
      • 代码
      • 提交答案
      • 优化
        • 代码实现
        • 结论
        领券
        问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档