题解 | #最长公共子串#

假设dp[i][j]为在str1的i索引位开始和str2的j索引位开始的最长公共子串。

所以当str1[i] == str2[j] and i < len(str1)-1 and j < len(str2) -1时，

dp[i][j] = dp[i+1][j+1] + 1

当str1[i] == str2[j] and i == len(str1)-1 and j == len(str2)-1时，

dp[i][j] = 1

else： dp[i][j] = 0

这样我们倒序循环两个数组就可以获得完整的dp，其中获取dp的最大值及其所在的下标就能得到想要的字符串。完整代码如下：

class Solution:
    def LCS(self , str1 , str2 ):
        # write code here
        n1 = len(str1)
        n2 = len(str2)
        begin = 0
        max = 0
        dp = [[0]*n2 for i in range(n1)]
        for i in range(n1-1,-1,-1):
              for j in range(n2-1,-1,-1):
                    if(str2[j] == str1[i] and i < n1-1 and j < n2-1):
                        dp[i][j] = dp[i+1][j+1] + 1
                    elif(str2[j] == str1[i] and (i == n1-1 or j == n2-1)):
                        dp[i][j] = 1
                    else:
                        dp[i][j] = 0
                    if(max < dp[i][j]):
                        max = dp[i][j]
                        begin = i
        return str1[begin:begin+max]