题解 | #LCS#

#
# longest common substring
# @param str1 string字符串 the string
# @param str2 string字符串 the string
# @return string字符串
#
# 状态转移比子序列简单；用两个变量记录最大长度和末位位置

class Solution:
    def LCS(self , str1 , str2 ):
        # write code here
        m = len(str1)
        n = len(str2)
        dp = [[0 for _ in range(n+1)] for _ in range(m+1)]
        lo,hi = 0,0
        max_length = 0
        max_end_str1 = 0
        for i in range(1,m+1):
            for j in range(1,n+1):
                if str1[i-1] == str2[j-1]:
                    dp[i][j] = dp[i-1][j-1]+1
                else:
                    dp[i][j] = 0
                if dp[i][j] > max_length:
                    max_length = dp[i][j]
                    max_tail_str1 = i
        return str1[max_tail_str1-max_length:max_tail_str1]