最长公共子序列
def get_long_common_string(s1: str, s2: str):
len1 = len(s1)
len2 = len(s2)
if len1 is 0 or len2 is 0:
return 0
if s1[0] == s2[0]:
return get_long_common_string(s1[1:], s2[1:]) + 1
return max(get_long_common_string(s1[1:], s2), get_long_common_string(s1, s2[1:]))
print(get_long_common_string('obeta', 'qty'))
最长公共子串
def get_long_common_sub(s1: str, s2: str):
big_long = 0
box = [[0] * len(s2)] * len(s1)
for i, str1 in enumerate(s1):
for j, str2 in enumerate(s2):
if str1 == str2:
if i < 1 and j < 1:
box[i][j] = 1
continue
box[i][j] = box[i - 1][j - 1] + 1
if box[i][j] > big_long:
big_long = box[i][j]
return big_long
print(get_long_common_sub('obeta', 'boy'))
最长相同字符子串
时间空间复杂度都为O(n)
.
def get_long_same_sub(s1: str):
len_str = len(s1)
# 长度为0时
if len_str == 0:
return 0
long = 1 # 子串最短长度
big_long = 1 # 子串最长长度
for i, s in enumerate(s1):
if i != len_str - 1: # 防止越界
if s == s1[i + 1]:
# 当前字符与下一个字符相同时加1
long += 1
if long > big_long:
big_long = long
else:
long = 1 # 重新开始计算下一轮
return big_long
print(get_long_same_sub('zhouyuexxxie'))
最长不重复子串
def get_long_repeat_sub(s):
if s is '':
return 0
result = ''
curr = ''
for sub in s:
if sub in curr:
# 当前字符在最近的不重复字符中
if len(curr) > len(result):
# 记录当前最大的不重复子串
result = curr
curr = curr[curr.index(sub) + 1:] + sub # 核心点, 跳过遇到的重复子串,比如"ohomm"中遇到第二个"o"的时候(此时curr="oh")继续使用"h",因此curr="h" + "o", 这可以减少大量已知的文本计算
else:
curr += sub
return max(
len(result),
len(curr), # 防止输入为 " " 的情况
)