题目描述
给定两个字符串text1和text2，返回这两个字符串的最长公共子序列的长度。如果不存在公共子序列，返回0。
一个字符串的子序列是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
例如，"ace"是"abcde"的子序列，但"aec"不是"abcde"的子序列。
两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。
样例
-
示例 1：
输入：text1 = "abcde", text2 = "ace"
输出：3
解释：最长公共子序列是"ace"，它的长度为3。 -
示例 2：
输入：text1 = "abc", text2 = "abc"
输出：3
解释：最长公共子序列是"abc"，它的长度为3。 -
示例 3：
输入：text1 = "abc", text2 = "def"
输出：0
解释：两个字符串没有公共子序列，返回0。
题目评估
知识点：动态规划
难度：中等
分析
本题可以使用动态规划来解。
当text1[i]=text2[j]时，text1[0..i]和text2[0..j]的最大公共子序列长度可由text1[0..i-1]和text2[0..j-1]的最大公共子序列长度+1获得。
当text1[i]!=text2[j]时，text1[0..i]和text2[0..j]的最大公共子序列长度为
Max（text1[0..i-1]和text2[0..j]的最大公共子序列长度， text1[0..i]和text2[0..j-1]的最大公共子序列长度）。
由此可以得到转移公式（其中dp数组记录长度）
图解：
Java代码题解
class Solution {
public int longestCommonSubsequence(String text1, String text2) {
if (text1.length() == 0 || text2.length() == 0) { // 如果任意字符串长度为0直接返回0
return 0;
}
// text1的长度为text1.length() = n
// text2的长度为text2.length() = m
// 开辟一个n+1行m+1列的数组
int[][] dp = new int[text1.length() + 1][text2.length() + 1];
for (int i = 1; i < dp.length; i++) { // 遍历text1的长度为i的子串text1[0..i]
char ch1 = text1.charAt(i - 1); // 取出当前字符text1[i]
for (int j = 1; j < dp[i].length; j++) { // 遍历text2的长度为j的子传text2[0..j]
char ch2 = text2.charAt(j - 1); // 去除当前字符text2[j]
if (ch1 == ch2) {
// 如果当前字符text1[i]=text2[j]
// text1[0..i]与text2[0..j]的最大公共子序列的长度 等于 text1[0..i-1]与text2[0..j-1]的最大公共子序列的长度+1
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
// 如果当前字符text1[i]!=text2[j]
// text1[0..i-1]与text2[0..j]的最大公共子序列的长度，text1[0..i]与text2[0..j-1]的最大公共子序列的长度
// 哪个大，哪个就是text1[0..i]与text2[0..j]的最大公共子序列的长度
dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j]);
}
}
}
return dp[dp.length - 1][dp[0].length - 1]; // 返回dp[n][m]
}
}
复杂度分析
设n是text1的长度，m为text2的长度，则时间复杂度为O(nm)。
因为创建了一个n+1行m+1列的数组，空间复杂度为O(nm)。