1143.最长公共子序列

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

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

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

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

示例 1：

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

示例 2：

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

线性dp

子序列问题本质就是选or不选，考虑最后一对字母，分别叫x和y，那么有4种情况

  • 不选x不选y
  • 不选x选y
  • 选x不选y
  • 选x选y

可以直接写出回溯表达式

那么有2个问题需要关注：

  • 在s[i]=t[j]时，真的需要dfs(i-1,j)和dfs(i,j-1)吗？
  • 在s[i]!=t[j]时，需要dfs(i-1,j-1)吗？

这两个问题的答案都是否定的，在s[i]=t[j]时，只需要直接dfs(i-1,j-1)即可，可以从数学角度证明，dfs(i-1,j)和dfs(i,j-1)的结果都不如dfs(i,j)

而s[i]!=t[j]，不需要dfs(i-1,j-1)，因为dfs(i,j-1)和dfs(i-1,j)会递归到dfs(i-1,j-1)

很自然的写出dp代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    // 主方法，计算两个字符串的最长公共子序列长度
    public int longestCommonSubsequence(String text1, String text2) {
        int n = text1.length(); // 获取第一个字符串的长度
        int m = text2.length(); // 获取第二个字符串的长度
        // 初始化二维数组 f，大小为 (n+1) x (m+1)
        int[][] f = new int[n + 1][m + 1];

        // 遍历第一个字符串的每个字符
        for (int i = 0; i < n; i++) {
            // 遍历第二个字符串的每个字符
            for (int j = 0; j < m; j++) {
                // 如果两个字符相等，说明最长公共子序列长度增加 1
                if (text1.charAt(i) == text2.charAt(j)) {
                    f[i + 1][j + 1] = f[i][j] + 1;
                } else {
                    // 否则，最长公共子序列长度取决于 f[i+1][j] 和 f[i][j+1] 的较大值
                    f[i + 1][j + 1] = Math.max(f[i][j + 1], f[i + 1][j]);
                }
            }
        }
        // 返回最终的最长公共子序列长度，即 f[n][m]
        return f[n][m];
    }
}

用二维数组是因为上一行的状态会被下一行所覆盖掉，如果用临时变量存储上一个状态即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
    // 主方法，计算两个字符串的最长公共子序列长度
    public int longestCommonSubsequence(String text1, String text2) {
        // 将第二个字符串转换为字符数组，方便访问每个字符
        char[] t = text2.toCharArray();
        int m = t.length; // 获取第二个字符串的长度
        // 初始化一维数组 f，大小为 m+1，用于存储动态规划的中间结果
        int[] f = new int[m + 1];

        // 遍历第一个字符串的每个字符
        for (char x : text1.toCharArray()) {
            
            // 初始化 pre 变量，用于保存 f[j+1] 的前一个状态值
            int pre=0;
            for (int j = 0; j < m; ++j) {
                int tmp = f[j + 1]; // 保存当前 f[j+1] 的值
                // 如果字符相等，则当前状态 f[j+1] 等于 pre + 1，否则取当前状态和前一个状态的较大值
                f[j + 1] = x == t[j] ? pre + 1 : Math.max(f[j + 1], f[j]);
                pre = tmp; // 更新 pre 为当前 f[j+1] 的值
            }
        }

        // 返回最终的最长公共子序列长度，即 f[m]
        return f[m];
    }
}