【数组篇】在python中如何查找最长字符串子串
"""
给定一个字符串，查找不重复字符的最长子字符串的长度。
例子：给定“abcabcbb”，答案是“abc”，长度是3。
给定“bbbbb”，答案是“b”，长度为1。
给定“pwwkew”，答案是“wke”，长度为3。
注意，答案必须是一个子串，“pwke”是一个子序列而不是一个子串。
"""
def longest_non_repeat_v1(string):
"""
查找不重复字符的最长子字符串的长度。
"""
if string is None:
return 0
dict = {}
max_length = 0
j = 0
for i in range(len(string)):
if string[i] in dict:
j = max(dict[string[i]], j)
dict[string[i]] = i + 1
max_length = max(max_length, i - j + 1)
return max_length
def longest_non_repeat_v2(string):
"""
查找不重复字符的最长子字符串的长度。
使用替代算法。
"""
if string is None:
return 0
start, max_len = 0, 0
used_char = {}
for index, char in enumerate(string):
if char in used_char and start <= used_char[char]:
start = used_char[char] + 1
else:
max_len = max(max_len, index - start + 1)
used_char[char] = index
return max_len
# 获取上面的函数，返回最大长度和子字符串
def get_longest_non_repeat_v1(string):
"""
查找不重复字符的最长子字符串的长度。
将max_len和子字符串作为元组返回
"""
if string is None:
return 0, ''
sub_string = ''
dict = {}
max_length = 0
j = 0
for i in range(len(string)):
if string[i] in dict:
j = max(dict[string[i]], j)
dict[string[i]] = i + 1
if i - j + 1 > max_length:
max_length = i - j + 1
sub_string = string[j: i + 1]
return max_length, sub_string
def get_longest_non_repeat_v2(string):
"""
查找不重复字符的最长子字符串的长度。
使用替代算法。
将max_len和子字符串作为元组返回
"""
if string is None:
return 0, ''
sub_string = ''
start, max_len = 0, 0
used_char = {}
for index, char in enumerate(string):
if char in used_char and start <= used_char[char]:
start = used_char[char] + 1
else:
if index - start + 1 > max_len:
max_len = index - start + 1
sub_string = string[start: index + 1]
used_char[char] = index
return max_len, sub_string
领取方式