面试题-python3 找出两个字符串中最大公共子字符串
前言
算法题(语言不限): 找出两个字符串中最大公共子字符串，如”abjeccarde”，”sjdgcargde”的最大子串为”car”
最大公共子字符串
解决思路：
1.先遍历a的子字符串
2.判断a的子字符串同时也在字符串b里，添加到f列表
3.最后f列表里面取出最后一个，就是最长的子串了
# 作者-上海悠悠 QQ交流群:717225969 # blog地址 https://www.cnblogs.com/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地址 https://www.cnblogs.com/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地址 https://www.cnblogs.com/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地址 https://www.cnblogs.com/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地址 https://www.cnblogs.com/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’]
2021年第七期《python接口自动化+测试开发》课程，4月18号开学（火热报名中！）
本期上课时间：4月18号-7月11号，每周六、周日晚上20:30-22:30