⾯试题-python3出两个字符串中最⼤公共⼦字符串前⾔字符串长度0到59
算法题(语⾔不限): 出两个字符串中最⼤公共⼦字符串，如"abjeccarde"，"sjdgcargde"的最⼤⼦串为"car"
最⼤公共⼦字符串
解决思路：
1.先遍历a的⼦字符串
2.判断a的⼦字符串同时也在字符串b⾥，添加到f列表
3.最后f列表⾥⾯取出最后⼀个，就是最长的⼦串了
# 作者-上海悠悠 QQ交流:717225969
# blog地址 wwwblogs/yoyoketang/
a = "abjeccarde"
b = "sjdgcargde"
f = []
# i是字串长度，从1到len(a)
for i in range(1, len(a)+1):
# j是下标位置
for j in range(len(a)+1-i):
e = a[j:j+i]
# 判断字串同时也在b，添加过去
if e in b:
f.append(e)
print(f)
# -1是取出最长的
print(f[-1])
运⾏结果：
['a', 'j', 'e', 'c', 'c', 'a', 'r', 'd', 'e', 'ca', 'ar', 'de', 'car']
car
上⾯的解决思路，虽然没太⼤问题，得到的结果是⼀样的，但是这题考的是算法。
要出最长的⼦串，可以先从长的⼦串遍历，判断符合条件就应该⽴即结束，没必要继续往下了。
⼦串
出两个字符串中最⼤公共⼦字符串，如"abjeccarde"，"sjdgcargde"的最⼤⼦串为"car"。
这⼜是⼀个⼦串的问题，跟前⾯解决思路是⼀样的，先遍历所有的⼦串
# 作者-上海悠悠 QQ交流:717225969
# blog地址 wwwblogs/yoyoketang/
# 遍历a得到所有的⼦串
a = "abjeccarde"
b = "absjdgcargde"
f = []
for i in range(1, len(a)+1):
for j in range(len(a)-i+1):
# ⽣成字串的组合
new_s = a[j:j+i]
f.append(new_s)
print(f)
运⾏结果
['a', 'b', 'j', 'e', 'c', 'c', 'a', 'r', 'd', 'e',
'ab', 'bj', 'je', 'ec', 'cc', 'ca', 'ar', 'rd', 'de',
'abj', 'bje', 'jec', 'ecc', 'cca', 'car', 'ard', 'rde',
'abje', 'bjec', 'jecc', 'ecca', 'ccar', 'card', 'arde',
'abjec', 'bjecc', 'jecca', 'eccar', 'ccard', 'carde',
'abjecc', 'bjecca', 'jeccar', 'eccard', 'ccarde',
'abjecca', 'bjeccar', 'jeccard', 'eccarde',
'abjeccar', 'bjeccard', 'jeccarde',
'abjeccard', 'bjeccarde',
'abjeccarde']
题⽬是要求出最长的⼦串，于是可以反着遍历，⼦串长度从最长到最⼩
# 作者-上海悠悠 QQ交流:717225969
# blog地址 wwwblogs/yoyoketang/
a = "abjeccarde"
b = "absjdgcargde"
f = []
for i in range(len(a), 0, -1):
for j in range(len(a)-i+1):
# ⽣成字串的组合
new_s = a[j:j+i]
f.append(new_s)
print(f)
于是打印结果
['abjeccarde',
'abjeccard', 'bjeccarde',
'abjeccar', 'bjeccard', 'jeccarde',
'abjecca', 'bjeccar', 'jeccard', 'eccarde',
'abjecc', 'bjecca', 'jeccar', 'eccard', 'ccarde',
'abjec', 'bjecc', 'jecca', 'eccar', 'ccard', 'carde',
'abje', 'bjec', 'jecc', 'ecca', 'ccar', 'card', 'arde',
'abj', 'bje', 'jec', 'ecc', 'cca', 'car', 'ard', 'rde',
'ab', 'bj', 'je', 'ec', 'cc', 'ca', 'ar', 'rd', 'de',
'a', 'b', 'j', 'e', 'c', 'c', 'a', 'r', 'd', 'e']
出公共的⼦串
已经遍历出a的⼦串了，于是判断⼦串也同时在b⾥⾯就可以了, 到之后⽤break跳出循环# 作者-上海悠悠 QQ交流:717225969
# blog地址 wwwblogs/yoyoketang/
a = "abjeccarde"
b = "absjdgcargde"
f = []
# 遍历查字串长度从最长到1
for i in range(len(a), 0, -1):
for j in range(len(a)+1-i):
e = a[j:j+i]
if e in b:
f.append(e)
# 符合条件就结束跳出循环
break
if f:
break  # 跳出外⾯的循环
print(f[0] if f else None)
运⾏结果：car
如果考虑到有多个值符合条件，可以去掉⾥层的break
# 作者-上海悠悠 QQ交流:717225969
# blog地址 wwwblogs/yoyoketang/
a = "abjeccardek"
b = "absjdgcargdek"
f = []
# 遍历查字串长度从最长到1
for i in range(len(a), 0, -1):
for j in range(len(a)+1-i):
e = a[j:j+i]
if e in b:
f.append(e)
# # 符合条件就结束跳出循环，考虑到多个值，去掉⾥层break
# break
if f:
break  # 跳出外⾯的循环
print(f)
运⾏结果：['car', 'dek']

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。