LeetCode刷题【1143】最长公共子序列

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

一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。

• 例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。

两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。

 

示例 1：

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

示例 2：

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

示例 3：

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

 

提示：

• 1 <= text1.length, text2.length <= 1000
• text1 和 text2 仅由小写英文字符组成。

经典动态规划问题

这样一个思路，分别假设text1和text2长度从0开始生长到最长长度的时候的情况。

如图中举例，text1 = "qcssopd"，text2 = "abcsdku"，

1. 当text1或者text2长度都为0的时候最长公共子序列的长度显然为0，此时可以把左边一竖排和最顶上一横排的值都填上0
2. 当text1为“q”，text2从“a”依次增加到全长度的时候可以非常简单的判断得到最长公共子序列长度都为0
3. 当text1为“qc”的时候，text2从“a”依次增加到全长度，可以明显的知道，直接拿字符串“c”和text2上的每一位字符对比，如果相等肯定表示有了一个最长公共子序列“c”
4. 这一步是重点，text1变换为“qcs”，text2从“a”依次增加到全长度，当text2的值为“abcs”的时候，我们可以知道末尾字符串字符相同，所以可以把这个问题转变为“qc”和“abc”的最长公共子序列的长度加1，而“qc”和“abc”的最长公共子序列长度我们在之前上一步3中已经得到了为1，所以此时的最长公共子序列长度为2。后面同理
5. 如果末尾字符串不相等的情况，举例text1=“qcs”，text2=“abc”，这个情况可以转换为“qc”与“abc”的最长公共子序列或者“qcs”与“ab”的公共子序列中较大的一个。
6. 后面依次循环执行4、5部分的逻辑

所以我们得到了状态转移方程

//当前字符相同的情况
dp[i][j] = dp[i-1][j-1]+1;
//当前字符不相同的情况
dp[i][j] = max( dp[i][j-1], dp[i-1][j]);

代码

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int[][] dp = new int[text1.length()+1][text2.length()+1];
        for (int row = 1; row <= text1.length(); row++) {
            for (int col = 1; col <= text2.length(); col++) {
                if (text1.charAt(row-1) == text2.charAt(col-1)){
                    dp[row][col] = dp[row-1][col-1]+1;
                }else{
                    dp[row][col] = Math.max(dp[row-1][col],dp[row][col-1]);
                }
            }
        }
        return dp[text1.length()][text2.length()];
    }
}

而，如果再扩展一下，想要知道最长公共子序列是啥的话，只需要在长度发生变化的时候把新增进来的字符记录下来即可。

该字符串最长公共子序列的查找的算法，我们比较直观的能想到的用法在两段文本内容相似度比较，或者文本变更内容查找之类的地方