二维dp与最长公共子串 2020-04-01

给定两个字符串s1 和 s2，返回这两个字符串的最长公共子序列

这是关于2个字符串的dp模板问题

以
s1 = 'ace'
s2 = 'babcde'为例
dptable如下

最长公共子序列的dptable
图片源于leetcode
为了方便初始化dp的base case，可以看到在规模为len1 * len2的dp表上外扩了一行+一列，表示字符串为''的情况

那么我们根据状态转移方程

if str1[i] == str2[j]:
    # 当前相同元素纳入最长公共子序列
    dp[i][j] = dp[i-1][j-1] + str1[i]
else:
    # 取左元素或者上元素中长度最长的一个
    if len(dp[i-1][j]) > len(dp[i][j-1]):
        dp[i][j] = dp[i-1][j]
    else:
        dp[i][j] = dp[i][j-1] 

如图所示：

dp二维数组的状态转移图

class Solution:
    def longestCommonSubsequence(self, str1, str2) -> int:
        m, n = len(str1), len(str2)

        # 构建 DP table 和 base case。注意，dp table的规模是(m+1)*(n+1)，都外扩了一层作为base case
        dp = [['' for i in range(n+1)] for j in range(m + 1)]
        
        # 开始填dp表
        for i in range(1, m + 1):
            for j in range(1, n + 1):

                # 进行状态转移
                # 如果两个指针指向的元素相等
                if str1[i - 1] == str2[j - 1]:
                    # 找到一个 lcs 中的字符
                    dp[i][j] = dp[i-1][j-1] + str1[i - 1]
                # 如果两个指针指向的元素不等
                else:
                    if len(dp[i-1][j]) > len(dp[i][j-1]):
                        dp[i][j] = dp[i-1][j]
                    else:
                        dp[i][j] = dp[i][j-1]

        # 返回最长公共子串长度    
        return len(dp[-1][-1])
        # # 返回最长公共子串
        # return dp[-1][-1]