本文主要是介绍【LeetCode】NO.3无重复字符的最长子串,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
NO.3无重复字符的最长子串
原题:
给定一个字符串,找出不含有重复字符的最长子串的长度。
示例 1:
输入: "abcabcbb"输出: 3
解释: 无重复字符的最长子串是 "abc",其
长度为 3。
示例 2:
输入: "bbbbb"输出: 1
解释: 无重复字符的最长子串是 "b"
,其长度为 1。
示例 3:
输入: "pwwkew"输出: 3 解释: 无重复字符的最长子串是"wke"
,其长度为 3。请注意,答案必须是一个子串,"pwke"
是一个子序列 而不是子串。
昨天上课老师刚好在讲字符串,没有听课偷偷把这个题给刷了,快下课的时候已经在写第二种方法了,废话不说直接上解析。
解析:
首先想到就是简单粗暴的逐个检查所有的子字符串,看它是否不含有重复的字符。不用想执行效率很低。
ef Substring(s):if s == '':return 0if len(s) == 1:return 1record = 0for i, char in enumerate(s):li1 = set()for st in s[i:]:if st not in li1:li1.add(st)if len(li1) > record:record = len(li1)else:breakreturn record
第二种方法解题思路:
借助一个辅助键值对来存储某个元素最后一次出现的下标。用一个整形变量存储当前无重复字符的子串开始的下标。
def Substring(s):max_len = 0 # 判断传入的字符串是否为空if s is None or len(s) == 0:return max_len # 定义一个字典, #存储不重复的字符和字符所在的下标str_dict = {}# 存储每次循环中最长的子串长度one_max = 0 # 记录最近重复字符所在的位置+1start = 0for i in range(len(s)): # 判断当前字符是否在字典中和当前字符的下标 #是否大于等于最近重复字符的所在位置if s[i] in str_dict and str_dict[s[i]] >= start: # 记录当前字符的值+1start = str_dict[s[i]] + 1 # 在此次循环中,最大的不重复子串的长度one_max = i - start + 1# 把当前位置覆盖字典中的位置str_dict[s[i]] = i # 比较此次循环的最大不重复子串长度 #和历史循环最大不重复子串长度max_len = max(max_len, one_max)return max_len
【推荐阅读】
汇总|这个公众号到底在写啥?
机器学习实战--住房月租金预测(2)
一道课后练习题背后的知识点
【Python爬虫】初识爬虫(1)
【LeetCode】贪心算法--买卖股票的最佳时机 II(122)
这篇关于【LeetCode】NO.3无重复字符的最长子串的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!