专栏首页程序员的知识天地leetcode无重复字符的最长字串 python实现

leetcode无重复字符的最长字串 python实现

无重复字符的最长字串是一道字符串处理算法的题目,在日常编程中,处理字符串是常见任务。用Python来实现leetcode这道算法题,该题目会涉及到一个概念“滑动窗口”。

一、题目描述

给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度(Longest substring without repeating characters)。

示例 1:

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

示例 2:

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

示例 3:

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

二、解题思路

先来定义一下“子串”,根据题目描述,“子串”就是字符串中截取某一部分,长度从1到该字符串的长度。比如“abc”的子串集合是:

[‘a’, ‘b’, ‘c’, ‘ab’, ‘bc’, ‘abc’]

用 Python 生成这个集合很容易,你是否想到了?

def subs(s: str):
    results = []
    for begin in range(len(s)):
        for length in range(len(s)-begin):
            results.append(s[begin:begin + length + 1])
    return results
z = subs('abcde')
print(z)

那么问题来了,任意长度为n的字符串一共有多少个这样的“子串”呢?答案是:(n+1) * n / 2 。从上面的例子很容易得出这个答案:begin等于0时,长度可以有 n – 0 个,begin等于1时,长度可以有 n – 1个,以此类推,总数就是:

n + (n-1) + … + 1 => (n+1)*n / 2

(1)暴力解法

明白了“子串”的概念和获取方法,自然而然的就得到了最朴素也是最“暴力”的解法:遍历字符串得到所有“子串”,然后判断每个“子串”是否有重复字符,最终就会得到无重复最长子串了。

这个“暴力”算法中,计算所有子串的时间复杂度是 O(n2),而判断一个子字符串是否有重复字符,又要从头到尾遍历一遍该字符串,所有最终的时间复杂度可以达到 O(n3)。

这个解法是不能被接受的,提到它全是因为前面对“子串”的解释及其数量计算,来练习Python对字符串的操作。

(2)滑动窗口

“滑动窗口”这个概念在计算机算法中非常常见。该算法可以把嵌套的循环转化为单循环从而降低时间复杂度。它在很多不同的领域都有应用:

TCP协议的滑动窗口进行流量控制

NLP(自然语言处理)中的 N-gram

图像处理中的物体识别

有兴趣的同学可以深入了解上面提到的应用领域。

大家在学python的时候肯定会遇到很多难题,以及对于新技术的追求,这里推荐一下我们的Python学习扣qun:784758214,这里是python学习者聚集地!!同时,自己是一名高级python开发工程师,从基础的python脚本到web开发、爬虫、django、数据挖掘等,零基础到项目实战的资料都有整理。送给每一位python的小伙伴!每日分享一些学习的方法和需要注意的小细节

点击:python技术分享交流

下面我们看看,“滑动窗口”如何进行字符串处理。结合题目中的例子“abcabcbb”这个字符串,我们来看看如何找它的无重复最长子串。

首先,我们定义窗口的两端:begin和end,分别表示要找的子串的开头和结尾。

开始的时候,begin和end都指向0的位置即‘a’,然后end不断后移(窗口变宽),当遇到第二个‘a’时(遇见重复字符)就得到一个子串,其长度就是end和begin位置的差。

不重复最长字串算法演示

如何判断是否遇到了重复字符‘a’呢?需要一个字典作为辅助数据结构,把end从头开始遇到的每个字符及其索引位置都放到字典里面,end每次移动到新字符就查一下字典即可。

通过字典,我们遇到第二个‘a’时就可以找到存在字典里面的第一个‘a’的位置。为了继续寻找无重复子串,begin就要指向第一个‘a’后面一个的位置即‘b’。然后end继续后移到‘b’,有发现它与前面的‘b’重复,计算子串长度赋值给最大长度(需要比较),同时begin要移动第一个‘b’后面的位置即‘c’。

这样依次移动end到字符串末尾就可以找到最长的子串,“子串窗口”也就从头移到了末尾。而只需要end从头到尾的一次循环即可。

把这个过程用Python实现如下:

class Solution:
    def lengthofLongestSubstring(self, s: str) -> int:
        maxlen = 0
        memo = dict()
        begin, end = 0, 0
        n = len(s)
        while end < n:
            last = memo.get(s[end])
            memo[s[end]] = end
            if last is not None:
                maxlen = max(maxlen, end-begin)
                begin = max(begin, last + 1)
            end += 1
        maxlen = max(maxlen, end-begin)
        return maxlen

提交后就可以看到结果。“执行时间”还只是个参考,再一次提交相同代码结果不是图中的击败91%,而变成了百分之十几。

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Python爬虫新手教程: 知乎文章图片爬取器

    昨天写了知乎文章图片爬取器的一部分代码,针对知乎问题的答案json进行了数据抓取,博客中出现了部分写死的内容,今天把那部分信息调整完毕,并且将图片下载完善到代码...

    一墨编程学习
  • Python 爬虫新手教程:抓取中国顶级编程网站上的优质文章

    首先浏览器输入 https://www.oschina.net/ 进入开源中国官网,点击顶部导航栏的 “博客” 选项进入博客列表页面,之后点击左侧 “服务端开发...

    一墨编程学习
  • 黑客程序员要想攻击阿里巴巴需要多强的技术?

    之前网上有很多人讨论过,为什么黑客不敢攻击阿里巴巴。其实自阿里这些年发展迅猛之时有不少次都遭遇过黑客的攻击,同时可以说有很多黑客团队都一直窥嘘着想要攻破阿里的技...

    一墨编程学习
  • 从零打卡leetcode之day 4--无重复最长字符串

    说明:有点抱歉,昨晚发的记得有写题目描述,但不知为啥,题目描述丢失了,可能是自己突然不小心删除了。

    帅地
  • 剑指Offer的学习笔记(C#篇)-- 左旋转字符串

    举例子吧。ABC DEF -- -- DEF ABC (变前三位就这样了)

    WeiMLing
  • 业界 | GitHub 年度报告盘点:开发者增至 3100 万,开源项目达 9600 万

    AI 科技评论按:日前,GitHub 发布了一年一度的「Octoverse」报告,其中列出了一些年度(2017 年 10 月 1 日-2018 年 9 月 30...

    AI科技评论
  • Java 10正式发布,最新特性全解读

    美的让人心动
  • DataSet之间的赋值

    DataSet 一个具有很多内置方法的程序集,在绑定数据中,使用率非常之高,虽然没有自定义泛型灵活性高,强类型的数据严谨性,而且一次性加载所有数据也稍微影响性能...

    Dabelv
  • Oculus Touch今日开启预售,视频告诉你它可以这么玩

    VRPinea
  • Linux关于GPU的命令

    于小勇

扫码关注云+社区

领取腾讯云代金券

玩转腾讯云 有奖征文活动