题解 | 最长公共子串

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# longest common substring
# @param str1 string字符串 the string
# @param str2 string字符串 the string
# @return string字符串
#
class Solution:
    def LCS(self , str1: str, str2: str) -> str:
        # write code here
        n1,n2 = len(str1),len(str2)
        if n1<1 or n2<1:
            return ""
        dp = [[0]*n2 for _ in range(n1)]
        for i in range(n1):
            if str1[i] ==str2[0]:
                dp[i][0] = 1
        for i in range(n2):
            if str2[i] ==str1[0]:
                dp[0][i] = 1
        L  = 0
        res = ""
        for i in range(1,n1):
            for j in range(1,n2):
                if str1[i] == str2[j]:
                    dp[i][j] = dp[i-1][j-1] + 1
                    if dp[i][j]>L:
                       L = dp[i][j]
                       res = str1[i-L+1:i+1]
        return res
        
        

        

python不超时的动态规划