【LeetCode 算法练习】“无重复字符的最长子串(Longest Substring Without Repeating Characters)”问题的 Python3 解答

题目描述

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

示例

示例 1:

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

示例2:

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

示例3:

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

测试用例

abcabcbb    3
bbbbb   1
pwwkew  3
""      0
au      2
dvdf    3
cdd     2
ddc     2

解题思路

逐字符遍历字符串,记录第一个无重复子串s[0]。查看下一个字符是否被rStr所包含,不包含就将此字符加到rStr的末尾,直到找到一个已经包含在rStr中的字符,此时,这个无重复子串的长度就有了。依次方法,继续查找子串,并与当前已经找到的子串做比较,记录最长的子串长度即可。字符串遍历完毕,问题得解。

解答

class Solution:
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        sLen = len(s)
        if sLen < 1:
            return 0
        rLen = 1
        startIndex = 1
        endIndex = 0
        rStr = s[0]

        while startIndex != sLen != endIndex:
            for i in range(startIndex, sLen):
                if s[i] not in rStr:
                    endIndex = i + 1
                    rStr = s[startIndex - 1:endIndex]
                else:
                    break
            rLen = max(rLen, len(rStr))
            if startIndex != sLen:
                rStr = s[startIndex]
            startIndex = startIndex + 1
        return rLen

算法分析

上述算法用Python3实现的时候有一个边界问题,字符串为空的情况下长度为 0,返回此值即可,否则下面初始化第一个无重复子串就溢出了。

上述算法时间复杂度是O(n^2),并不理想。

中文官网的题目地址:无重复字符的最长子串

Python 算法 LeetCode 无重复字符的最长子串 解答 技术
本文更新于