【牛客剑指offer刷题】:Python:48. 最长不含重复字符的子字符串

描述

请从字符串中找出一个最长的不包含重复字符的子字符串,计算该最长子字符串的长度。
数据范围:
s.length≤40000

示例1

输入:
“abcabcbb”
返回值:3

说明:
因为无重复字符的最长子串是”abc”,所以其长度为 3。

示例2

输入:
“bbbbb”
返回值:1

说明:
因为无重复字符的最长子串是”b”,所以其长度为 1。

代码1:辅助队列:O(m*n)

#coding:utf-8
#
# 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
#
# 
# @param s string字符串 
# @return int整型
#
class Solution:
    def lengthOfLongestSubstring(self , s ):
        # write code here
        res = []
        if not s:
            return 0 
        max_num = 0 
        for i in s:
            if i in res:
                idx = res.index(i)
                res = res[idx+1:]
                res.append(i)
            else:
                res.append(i)
            max_num = max(len(res), max_num)
        return max_num

代码2:动态规划+hash表 :O(N)

哈希表统计: 遍历字符串 s 时,使用哈希表(记为 dic )统计 各字符最后一次出现的索引位置 。
左边界 i获取方式: 遍历到 s[j]时,可通过访问哈希表 dic[s[j]]获取最近的相同字符的索引 i。

时间复杂度 O(N) : 其中 N 为字符串长度,动态规划需遍历计算 dp 列表。
空间复杂度 O(1) : 字符的 ASCII 码范围为 0 ~ 127 ,哈希表 dic 最多使用 O(128) = O(1) 大小的额外空间。
《【牛客剑指offer刷题】:Python:48. 最长不含重复字符的子字符串》

#coding:utf-8
#
# 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
#
# 
# @param s string字符串 
# @return int整型
#
class Solution:
    def lengthOfLongestSubstring(self , s ):
        # write code here
        dic = { } # 存储当前字符上次出现的idx 
        max_n, last_max = 0, 0 
        for j in range(len(s)):
            i = dic.get(s[j], -1) # 上次该字符出现的位置
            if j - i > last_max:  # 如果出现 dvdf 这种f第一次出现的情况,需要判断一下是否是大于前一个最长串
                last_max += 1
            else:
                last_max = j - i 
            max_n = max(max_n, last_max)
            dic[s[j]] = j 
        return max_n 
    原文作者:Jack_Kuo
    原文地址: https://blog.csdn.net/weixin_37251044/article/details/121626211
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系博主进行删除。
点赞