leetcode 1143-最长公共子序列

题目描述

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

一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。 例如，“ace” 是 “abcde” 的子序列，但 “aec” 不是 “abcde” 的子序列。两个字符串的「公共子序列」是这两个字符串所共同拥有的子序列。

若这两个字符串没有公共子序列，则返回 0。

示例1 示例2 示例3 提示:

1 <= text1.length <= 1000 1 <= text2.length <= 1000 输入的字符串只含有小写英文字符。

题解

注意：涉及到数组相关的dp，dp的长度要多留一位，以便于处理空字符串，此外dp[i][j]对应于s1[i-1]和s2[j-1]

动态规划之最长子序列（LCS）

动态规划思路

第一步，一定要明确 dp 数组的含义

对于字符串 s1 和 s2，构造一个这样的 DP table： 其中，dp[i][j] 的含义是：对于 s1[1…i] 和 s2[1…j]，它们的 LCS 长度是 dp[i][j]。比如上图的例子，d[2][4] 的含义就是：对于 “ac” 和 “babc”，它们的 LCS 长度是 2。我们最终想得到的答案应该是 dp[3][6]。

第二步 定义 base case

我们让索引为 0 的行和列表示空串，dp[0][…] 和 dp[…][0] 都应该初始化为 0，这就是 base case。 比如说，按照刚才 dp 数组的定义，dp[0][3]=0 的含义是：对于字符串 “” 和 “bab”，其 LCS 的长度为 0。因为有一个字符串是空串，它们的最长公共子序列的长度显然应该是 0。

第三步 找状态转移方程

状态转移说简单些就是做选择，比如说这个问题，是求 s1 和 s2 的最长公共子序列，不妨称这个子序列为 lcs。那么对于 s1 和 s2 中的每个字符，有什么选择？很简单，两种选择，要么在 lcs 中，要么不在。 如果某个字符应该在 lcs 中，那么这个字符肯定同时存在于 s1 和 s2 中，因为 lcs 是最长公共子序列。所以本题的思路是这样： 用两个指针 i 和 j 从后往前遍历 s1 和 s2，如果 s1[i]==s2[j]，那么这个字符一定在 lcs 中；否则的话，s1[i] 和 s2[j] 这两个字符至少有一个不在 lcs 中，需要丢弃一个。具体到代码层面就是：

if(text1.charAt(i-1)==text2.charAt(j-1)){
                    dp[i][j]=dp[i-1][j-1]+1;
                }else{
                    dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1]);
                }

代码实现

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int len1 = text1.length();
        int len2 = text2.length();
        //dp[0][k]和dp[k][0]都为0,dp数组会自动初始化为0
        int[][] dp = new int[len1+1][len2+1];
        //i和j要从1开始，方便dp数组做处理
        for(int i=1;i<len1+1;i++){
            for(int j=1;j<len2+1;j++){
               //text1和text2的下标要比dp中少1
                if(text1.charAt(i-1)==text2.charAt(j-1)){
                    dp[i][j]=dp[i-1][j-1]+1;
                }else{
                    dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1]);
                }
            }
        }
        return dp[len1][len2];
    }
}