LeetCode 1143. 最长公共子序列

Categories:

Tags:

题目描述
思路分析
1. 解法一：动态规划（推荐）
相似题目

题目描述

✅ 1143. 最长公共子序列

思路分析

解法一：动态规划（推荐）

核心思路：

经典「双序列 DP」模型。

状态定义：dp[i][j] 表示 text1[0..i-1] 与 text2[0..j-1] 的最长公共子序列（LCS）长度。索引从 1 开始，dp[0][*] = dp[*][0] = 0 作为边界。

状态转移：

若 text1[i-1] == text2[j-1]（当前字符相同），可纳入 LCS： dp[i][j] = dp[i-1][j-1] + 1

否则（字符不同），无法同时使用两个当前字符，丢弃其中一个取最大： dp[i][j] = max(dp[i-1][j], dp[i][j-1])

举例：text1 = "abcde", text2 = "ace"
    ""  a   c   e
""   0   0   0   0
a    0   1   1   1
b    0   1   1   1
c    0   1   2   2
d    0   1   2   2
e    0   1   2   3
dp[5][3] = 3，LCS 为 "ace"。

复杂度分析：

时间复杂度：O(m × n)，其中 m、n 为两字符串长度，需填满二维 dp 表

空间复杂度：O(m × n)，存储 dp 数组；可用滚动数组优化至 O(n)

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++) {
                // 字符相同：当前字符纳入 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]);
                }
            }
        }
        return dp[m][n];
    }
}

func longestCommonSubsequence(text1 string, text2 string) int {
	m, n := len(text1), len(text2)
	dp := make([][]int, m+1)
	for i := range dp {
		dp[i] = make([]int, n+1)
	}
	for i := 1; i <= m; i++ {
		for j := 1; j <= n; j++ {
			// 字符相同：当前字符纳入 LCS
			if text1[i-1] == text2[j-1] {
				dp[i][j] = dp[i-1][j-1] + 1
			} else {
				// 字符不同：丢弃其中一个，取较大值
				dp[i][j] = max(dp[i-1][j], dp[i][j-1])
			}
		}
	}
	return dp[m][n]
}

相似题目

题目	难度	考察点
718. 最长重复子数组	中等	二维DP、最长公共子串
583. 两个字符串的删除操作	中等	二维DP、LCS变种
72. 编辑距离	中等	二维DP、字符串变换
516. 最长回文子序列	中等	二维DP、区间DP
97. 交错字符串	中等	二维DP、字符串匹配
1035. 不相交的线	中等	二维DP、本质是LCS
1092. 最短公共超序列	困难	二维DP、LCS 变种
2207. 字符串中最多数目的子序列	中等	贪心、子序列计数
2565. 最少得分子序列	困难	双序列DP

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/40931089