#P4099. 最长公共子序列
-
ID: 2336
Tried: 255
Accepted: 89
Difficulty: 5
最长公共子序列
题目描述
给定两个字符串 text1 和 text2，返回这两个字符串的 最长公共子序列 的长度。如果不存在公共子序列，则返回 0。
定义：
- 子序列：从原字符串中删除 某些字符（可不删除），但不改变剩余字符的 相对顺序，得到的新字符串。
- 公共子序列：两个字符串都包含的 子序列。
输入描述
输入包含两行：
- 第一行是字符串
text1（1≤∣text1∣≤1000）。 - 第二行是字符串
text2（1≤∣text2∣≤1000）。
text1 和 text2 仅由小写英文字符组成。
输出描述
输出一行，表示 最长公共子序列 的长度。
样例输入 1
abcde
ace
样例输出 1
3
说明：最长公共子序列是 "ace"，长度为 3。
样例输入 2
abc
abc
样例输出 2
3
说明：最长公共子序列是 "abc"，长度为 3。
样例输入 3
abc
def
样例输出 3
0
说明：两个字符串没有公共子序列，返回 0。
解题思路：动态规划
-
定义状态：
- 设 dp[i][j] 表示
text1[0:i]和text2[0:j]的 最长公共子序列 的长度。
- 设 dp[i][j] 表示
-
状态转移方程：
- 如果 text1[i−1]==text2[j−1]，则当前字符匹配：dp[i][j]=dp[i−1][j−1]+1
- 如果 text1[i−1]=text2[j−1]，则考虑去掉
text1[i-1]或text2[j-1]：dp[i][j]=max(dp[i−1][j],dp[i][j−1])
-
初始化：
- dp[0][j]=0（空字符串与
text2任何前缀的 LCS 长度为0） - dp[i][0]=0（空字符串与
text1任何前缀的 LCS 长度为0）
- dp[0][j]=0（空字符串与
-
遍历方向：
- 先遍历 i（
text1的前 i 个字符）。 - 再遍历 j（
text2的前 j 个字符）。
- 先遍历 i（
-
最终答案：
- dp[m][n] 即
text1[0:m]和text2[0:n]的最长公共子序列长度。
- dp[m][n] 即
-
时间复杂度： O(m×n)，其中 m 和 n 分别是
text1和text2的长度。 -
空间复杂度： O(m×n)。
Python 代码
import sys
def longest_common_subsequence(text1, text2):
""" 使用动态规划计算最长公共子序列长度 """
m, n = len(text1), len(text2)
# 初始化 DP 数组，dp[i][j] 表示 text1[0:i] 和 text2[0:j] 的最长公共子序列长度
dp = [[0] * (n + 1) for _ in range(m + 1)]
# 遍历 text1 和 text2
for i in range(1, m + 1):
for j in range(1, n + 1):
if text1[i - 1] == text2[j - 1]: # 字符匹配
dp[i][j] = dp[i - 1][j - 1] + 1
else: # 取去掉 text1[i-1] 或 text2[j-1] 的最大值
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
return dp[m][n] # 返回最长公共子序列的长度
def main():
""" 读取输入并调用求解函数 """
text1 = sys.stdin.readline().strip()
text2 = sys.stdin.readline().strip()
print(longest_common_subsequence(text1, text2))
if __name__ == "__main__":
main()
Java 代码
import java.util.*;
public class Main {
public static int longestCommonSubsequence(String text1, String text2) {
int m = text1.length(), n = text2.length();
// 初始化 DP 数组，dp[i][j] 表示 text1[0:i] 和 text2[0:j] 的最长公共子序列长度
int[][] dp = new int[m + 1][n + 1];
// 遍历 text1 和 text2
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 { // 取去掉 text1[i-1] 或 text2[j-1] 的最大值
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
return dp[m][n]; // 返回最长公共子序列的长度
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String text1 = sc.next();
String text2 = sc.next();
System.out.println(longestCommonSubsequence(text1, text2));
sc.close();
}
}
C++ 代码
#include <iostream>
#include <vector>
#include <string>
using namespace std;
int longestCommonSubsequence(string text1, string text2) {
int m = text1.size(), n = text2.size();
// 初始化 DP 数组，dp[i][j] 表示 text1[0:i] 和 text2[0:j] 的最长公共子序列长度
vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
// 遍历 text1 和 text2
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (text1[i - 1] == text2[j - 1]) { // 字符匹配
dp[i][j] = dp[i - 1][j - 1] + 1;
} else { // 取去掉 text1[i-1] 或 text2[j-1] 的最大值
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
return dp[m][n]; // 返回最长公共子序列的长度
}
int main() {
string text1, text2;
cin >> text1 >> text2; // 读取两个输入字符串
cout << longestCommonSubsequence(text1, text2) << endl;
return 0;
}