题目
输入一个字符串,返回该串中最长不含重复字符的子串长度
例子
- ‘abcabcbb’ -> 3
- ‘bbbbbb’ -> 1
##假设
- 输入的字符串一定不为None或空串
- 输入的字符串中的字符仅为小写英文字母
tips
- 枚举所有子串，判断子串是否重复
- 你能想出更优的解法吗
答案
解法1:
def lengthOfLongestSubstring(s):
longest = 1
for i in range(len(s)):
for j in range(i + 1,len(s)):
unique_length = len(set(s[i:j + 1]))
if unique_length == j - i + 1 and unique_length > longest:
longest = unique_length
return longest 性能
- 时间复杂度O(n^3)
- 空间复杂度O(n)
关键点
- 枚举所有子串进行判断
- 利用set()去除重复元素
解法2:
def lengthOfLongestSubstring(s):
# 哈希集合，记录每个字符是否出现过
occ = set()
n = len(s)
# 左指针，初始值为 -1，相当于我们在字符串的左边界的左侧，还没有开始移动
rk, ans = -1, 0
for i in range(n):
if i != 0:
# 左指针向右移动一格，移除一个字符
occ.remove(s[i - 1])
while rk + 1 < n and s[rk + 1] not in occ:
# 不断地移动右指针
occ.add(s[rk + 1])
rk += 1
# 第 i 到 rk 个字符是一个极长的无重复字符子串
ans = max(ans, rk - i + 1)
return ans 性能
- 时间复杂度O(n)
- 空间复杂度O(n)
关键点
- 双指针
算法描述
- 判断s是否在集合occ中，如果不在则添加。集合中存在的元素在字符串中是连续的
- 如果s在occ中，则会遍历删除occ中的元素，找到重复元素
解法3：
def lengthOfLongestSubstring(s):
"""
输出s中所有不含重复字符的子字符串
1. 判断临时字符串中是否含有字符，如果没有则初始化临时索引为索引值
2. 判断s中索引对应的值是否在临时字符串中，如果没有则在临时字符串中追加元素，索引加一
3. 如果有，则将临时字符串追加到字符串列表中，索引为临时索引加一，临时字符串清空
:param s: 原始字符串
:return:
"""
index = 0 # 索引
onlylist = [] # 字符串列表
onlychars = '' # 临时字符串
onlycharsindex = 0 # 临时索引
while index < len(s):
char = s[index]
if onlychars == '':
onlycharsindex = index
if char in onlychars: # O(n)
onlylist.append(onlychars)
index = s.index(char, onlycharsindex) + 1
onlychars = ''
continue
else:
onlychars += char
index += 1
onlylist.append(onlychars)
print(onlylist)
return max([len(chars) for chars in onlylist])性能
- 时间复杂度O(n)
- 空间复杂度O(nlogn)
关键点
- 存储不重复元素字符串