1143.最长公共子序列

题目描述

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

示例 1

输入: text1 = "abcde", text2 = "ace"
输出: 3

示例 2

输入: text1 = "abc", text2 = "abc"
输出: 3

示例 3

输入: text1 = "abc", text2 = "def"
输出: 0

解题思路：二维动态规划

设 dp[i][j] 为 text1 前 i 个字符与 text2 前 j 个字符的 LCS 长度。

转移：

• 若 text1[i-1] == text2[j-1]，dp[i][j] = dp[i-1][j-1] + 1。
• 否则 dp[i][j] = max(dp[i-1][j], dp[i][j-1])。

代码实现

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        String text1 = scanner.next();
        String text2 = scanner.next();

        Solution solution = new Solution();
        int result = solution.longestCommonSubsequence(text1, text2);
        System.out.println(result);

        scanner.close();
    }
}

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int m = text1.length(), n = text2.length();
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                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[m][n];
    }
}

空间优化：一维滚动

用一维数组 dp[j] 表示当前行 i 下的值，保存上一行左上角值 prev。

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        String text1 = scanner.next();
        String text2 = scanner.next();

        Solution solution = new Solution();
        int result = solution.longestCommonSubsequence(text1, text2);
        System.out.println(result);

        scanner.close();
    }
}

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int m = text1.length(), n = text2.length();
        int[] dp = new int[n + 1];
        for (int i = 1; i <= m; i++) {
            int prev = 0;
            for (int j = 1; j <= n; j++) {
                int tmp = dp[j];
                if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
                    dp[j] = prev + 1;
                } else {
                    dp[j] = Math.max(dp[j], dp[j - 1]);
                }
                prev = tmp;
            }
        }
        return dp[n];
    }
}

复杂度分析

• 时间复杂度：O(mn)。
• 空间复杂度：O(mn)（二维），优化为 O(n)（一维滚动）。

逐字符比对，等则斜对角加一，不等取左上两者最大；滚动数组以常数额外变量保留左上角值完成转移。