1. 首页
  2. 剑指offer经典面试题

[剑指 Offer 第 2 版第 48 题] “最长不重复字符串的子字符串”做题记录

[剑指 Offer 第 2 版第 48 题] “最长不重复字符串的子字符串”做题记录

第 48 题:最长不重复字符串的子字符串

传送门:最长不含重复字符的子字符串

请从字符串中找出一个最长的不包含重复字符的子字符串,计算该最长子字符串的长度。

假设字符串中只包含从’a’到’z’的字符。

样例:

输入:"abcabc"

输出:3

思路1:滑动窗口:

Python 代码:

  class Solution:
        def lengthOfLongestSubstring(self, s):
            """
            :type s: str
            :rtype: int
            """
            # 特判
            size = len(s)
            if size < 2:
                return size
            l = 0
            r = -1
            counter = [0 for _ in range(256)]
            res = 1
            while l < size:
                # 首先"右指针"不断向右边尝试,走到出现重复的最右边
                while r + 1 < size and counter[ord(s[r + 1])] == 0:
                    # 表示没有重复元素,r 可以加 1
                    counter[ord(s[r + 1])] += 1
                    r += 1
                # 此时,记录不重复子串是"左指针"固定时候最长
                res = max(res, r - l + 1)
                # 考虑移动"左指针"
                # 此时 s[r+1] 就是已经扫过的区间里重复的元素,要把它剔除出去
                while r + 1 < size and s[l] != s[r + 1]:
                    # 有重复元素,左边就要减 1
                    counter[ord(s[l])] -= 1
                    l += 1
                # 出了上一个循环以后,还要再把左指针向右移动一格,否则右指针不能向右移动
                counter[ord(s[l])] -= 1
                l += 1
            return res

思路2:动态规划

Python 代码:

  class Solution:
        def lengthOfLongestSubstring(self, s):
            """
            :type s: str
            :rtype: int
            """
            # 特判
            l = len(s)
            if l < 2:
                return l
            # dp[i] 表示以 s[i] 结尾的最长不重复子串的长度
            # 因为自己肯定是不重复子串,所以初始值设置为 1
            dp = [1 for _ in range(l)]
            map = dict()
            map[s[0]] = 0
            for i in range(1, l):
                if s[i] in map:
                    if i - map[s[i]] > dp[i - 1]:
                        dp[i] = dp[i - 1] + 1
                    else:
                        dp[i] = i - map[s[i]]
                else:
                    dp[i] = dp[i - 1] + 1
                # 设置字符与索引键值对
                map[s[i]] = i
            # 最后拉通看一遍最大值
            return max(dp)

思路3:隔板法

Python 代码:

  class Solution:
        def lengthOfLongestSubstring(self, s):
            # 特判
            l = len(s)
            if l < 2:
                return l
            # 隔板法
            # key:字符,val 出现的索引
            map = dict()
            point = 0
            res = 1
            for i in range(l):
                # 关键1:map[s[i]] >= point,等于是可以的
                if s[i] in map and map[s[i]] >= point:
                    # 先把隔板向后移动一位
                    point = map[s[i]] + 1
                # 然后记录最长不重复子串的长度
                res = max(res, i - point + 1)
                # 关键2:无论如何都更新位置
                map[s[i]] = i
            return res

参考资料:LeetCode 第 3 题:最长不重复字符串

作者:liweiwei1419

来源:https://liweiwei1419.github.io/sword-for-offer/


JS中文网,Javascriptc中文网是中国领先的新一代开发者社区和专业的技术媒体,一个帮助开发者成长的社区,是给开发者用的 Hacker News,技术文章由为你筛选出最优质的干货,其中包括:Android、iOS、前端、后端等方面的内容。目前已经覆盖和服务了超过 300 万开发者,你每天都可以在这里找到技术世界的头条内容。

本文著作权归作者所有,如若转载,请注明出处

转载请注明:文章转载自「 Java极客技术学习 」https://www.javajike.com

标题:[剑指 Offer 第 2 版第 48 题] “最长不重复字符串的子字符串”做题记录

链接:https://www.javajike.com/article/3294.html

« [剑指 Offer 第 2 版第 47 题] “礼物的最大值”做题记录
[剑指 Offer 第 2 版第 49 题] “丑数”做题记录»

相关推荐

QR code