【Leetcode】1143.最长公共子序列

1143.最长公共子序列

题目

给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。

注：两个字符串的「公共子序列」（Longest Common Subsequence，简称 LCS）是这两个字符串所共同拥有的子序列。若这两个字符串没有公共子序列，则返回 0。

示例 1:
输入：text1 = "abcde", text2 = "ace" 
输出：3  
解释：最长公共子序列是 "ace"，它的长度为 3。

示例 2:
输入：text1 = "abc", text2 = "abc"
输出：3
解释：最长公共子序列是 "abc"，它的长度为 3。

示例 3:
输入：text1 = "abc", text2 = "def"
输出：0
解释：两个字符串没有公共子序列，返回 0。

方法（动态规划）

遇到子序列相关的问题，可以往动态规划上考虑。这道题让我们在两个字符串中寻找共同拥有的最长子序列，因此很容易想到用二维动态规划来解决。

1.定义dp数组

定义$dp[i][j]$为：$str1[0…i-1]和str2[0…j-1]$的最长公共子序列长度。

2.Base Case

根据上述dp数组的定义，可以写出如下Base Case：

  • i为0时，str1[0…i-1]不构成一个字符串，因此不存在与str2的公共子序列，因此dp[0][j]为0
  • j为0时，str2[0…j-1]不构成一个字符串，因此不存在于str1的公共子序列，因此dp[i][0]为0

3.状态转移方程

当str1遍历到i - 1，str2遍历到j - 1时，即要求$str1[0…i-1]和str2[0…j-1]$的最长公共子序列长度时，需要考虑以下的几种情况：

  • 如果str1[i - 1]与str2[j - 1]相等，那么肯定要将其放入str1[0…i−1]和str2[0…j−1]的LCS当中，有了这个字符，LCS的长度就会加1，因此
    $$dp[i][j] = dp[i - 1][j - 1] + 1$$

  • 如果str1[i - 1]与str2[j - 1]不等，则又会分为以下的三种情况：

    • str1[i - 1]与str2[j - 1]都不放入LCS当中，那么LCS的长度不会产生变化，即dp[i][j] = dp[i - 1][j - 1]

    • str1[i - 1]放入LCS中，但str2[j - 1]不放。这时dp[i][j] = dp[i][j - 1]

    • str1[i - 1]不放入LCS中，但str2[j - 1]放。这时dp[i][j] = dp[i - 1][j]

      由于在dp[i][j]这个位置可以做上述三种选择，因此取三种选择可能产生的最大值，即为dp[i][j]。即：
      $$dp[i][j] = max(dp[i - 1][j - 1],dp[i][j - 1],dp[i - 1][j])$$

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public int longestCommonSubsequence(String str1, String str2) {
    int[][] dp = new int[str1.length() + 1][str2.length() + 1];
    //Base Case,其实可以不用，因为数组初始化时全体元素就为0
    for(int j = 0; j <= str2.length(); j++)
        dp[0][j] = 0;
    for(int i = 0; i <= str1.length(); i++)
        dp[i][0] = 0;
    for(int i = 1; i <= str1.length(); i++){
        for(int j = 1; j <= str2.length(); j++){
            if(str1.charAt(i - 1) == str2.charAt(j - 1))
                dp[i][j] = dp[i - 1][j - 1] + 1;
            else
                dp[i][j] = Math.max(dp[i - 1][j - 1], Math.max(dp[i][j - 1], dp[i - 1][j]));
        }
    }
    return dp[str1.length()][str2.length()];
}
  • 时间复杂度:O(m * n)
  • 空间复杂度:O(m * n)
    其中，m和n分别为str1和str2的长度