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

​无重复字符的最长字串是一道经典的额字符串处理算法的题目，日常编程过程中，处理字符串是很多见的。用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 resultsz = 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

图像处理中的物体识别

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

下面我们看看，“滑动窗口”如何进行字符串处理。结合题目中的例子“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%，而变成了百分之十几。

总结

以上是生活随笔为你收集整理的python leetcode_python实现leetcode中无重复字符的最长字串的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。