题目描述
给定两个字符串str1和str2,输出两个字符串的最长公共子串 题目保证str1和str2的最长公共子串存在且唯一。 (子串意味着是连续的)输入
"1AB2345CD","12345EF"
返回值
"2345"
动态规划法
先确定状态,f(i, j)表示str1中前i个字符和str2中前j个字符中的最长公共子序列的长度
但这样写不出状态转移方程,因为这里 求解公共连续字符串 是没法形成递推关系的,因此增加限制条件:
f(i, j)表示str1中前i个字符和str2中前j个字符中的最长公共子序列的长度,且以第i个字符和第j个字符为结尾
可以简单写出状态转移方程
str1[i] == str2[j] 时,f[i][j] = f[i-1][j-1] + 1
str1[i] != str2[j] 时,f[i][j] = 0
但还有个问题,这个动态规划不能直接得到答案,需要用变量maxLength保存最长的长度
边界条件为:
i = 0 或 j = 0 时, f[i][j] = 0
class Solution: def LCS(self , str1 , str2 ): maxLen = 0 endIndex = 0 f = [[0 for j in range(len(str2)+1)] for i in range(len(str1)+1)] for i in range(1, len(str1)+1): for j in range(1, len(str2)+1): if (str1[i-1] == str2[j-1]): f[i][j] = f[i-1][j-1] + 1 else: f[i][j] = 0 if maxLen < f[i][j]: maxLen = f[i][j] endIndex = i # end index of the first string # print(maxLen) return str1[endIndex-maxLen:endIndex]
此题可以对比 最长公共子序列 一起看
参考:
https://www.nowcoder.com/activity/oj