index-picture
1.最长公共子序列
问题情景：
假设你管理着网站dictionary.com。用户在该网站输入单词时，你需要给出其定义。
但如果用户拼错了，你必须猜测他原本要输入的是什么单词。例如，假设Alex不小心输入了fosh。那怎么知道他原本想输入的是fort还是fish呢?解答：
如果用最长公共子串，两个单词的最长公共子串长度都为2，所以改用最长公共子序列
网格图（图片来源《算法图解》）
最终判断想要输入的是fish这个单词！
-
Python3实现代码：
def LCS(string1,string2): len1 = len(string1) len2 = len(string2) res = [[0 for i in range(len1+1)] for j in range(len2+1)] # 创建一个二维数组，赋初始值为0 # i为行，j为列 for i in range(1,len2+1): for j in range(1,len1+1): if string2[i-1] == string1[j-1]: res[i][j] = res[i-1][j-1]+1 else: res[i][j] = max(res[i-1][j],res[i][j-1]) return res,res[-1][-1]
2.最长公共子串
问题情景：
求fish和hish的最长公共子串-
解答：
网格图（图片来源《算法图解》） -
python3代码：
def LCString(string1,string2): len1 = len(string1) len2 = len(string2) res = [[0 for i in range(len1+1)] for j in range(len2+1)] # 创建一个二维数组，赋初始值为0 result = 0 # 存储当前最长子串的长度 # i为行，j为列 for i in range(1,len2+1): for j in range(1,len1+1): if string2[i-1] == string1[j-1]: res[i][j] = res[i-1][j-1]+1 result = max(result, res[i][j]) return result
