最长公共子序列问题
作者：Grey
原文地址：
题目描述
给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。
一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。
两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。
题目链接: LeetCode 1143. Longest Common Subsequence
暴力解法
定义递归函数
int process(char[] str1, char[] str2, int i, int j)
递归含义表示：str1 从 0 开始一直到 i，str2 从 0 位置开始一直到 j，最长公共子序列是多少。
首先看 base case，
如果 i == 0 且 j == 0，说明 str1 和 str2 只有一个字符了，此时，如果str1[i] == str2[j] 则返回 1 ，表示最长公共子序列的长度就是 1， 否则则返回 0，表示最长公共子序列的长度就是 0；
如果 i == 0 且 j != 0，说明 str1 只有一个字符，而 str2 不止一个字符，此时如果str1[i] == str2[j]，说明最长公共子序列长度就是 1， 如果str1[i] != str2[j]，则让 i 继续去匹配 j - 1 位置，即process(str1, str2, i, j - 1);
同理，如果 j == 0 且 i!= 0，说明 str2 只有一个字符，而 str1 不止一个字符，此时如果str1[i] == str2[j]，说明最长公共子序列长度就是 1， 如果str1[i] != str2[j]，则让 j 继续去匹配 i - 1 位置，即process(str1, str2, i - 1, j);
base case 的逻辑如下
if (i == 0 && j == 0) {
return str1[i] == str2[j] ? 1 : 0;
}
if (i == 0) {
if (str1[i] == str2[j]) {
return 1;
}
return process(str1, str2, i, j - 1);
}
if (j == 0) {
if (str1[i] == str2[j]) {
return 1;
}
return process(str1, str2, i - 1, j);
}
接下来是普遍位置，即 i != 0 且 j != 0时，有如下几种情况
情况 1，最长公共子序列不要 i 位置;
int p1 = process(str1, str2, i - 1, j);
情况 2，最长公共子序列不要 j 位置;
int p2 = process(str1, str2, i, j - 1);
情况 3，最长公共子序列既要 i 位置，也要 j 位置，此时，需要满足条件 str[i] == str[j];
情况 4，最长公共子序列既不要 i 位置，也不要 j 位置；
情况 3 和 情况 4 整合成一条语句
int p3 = (str1[i] == str2[j] ? 1 : 0) + process(str1, str2, i - 1, j - 1);
最后，返回上述几种情况下的最大值
return Math.max(p2, Math.max(p1, p3));
暴力解法完整代码如下
class Solution {
public static int longestCommonSubsequence(String s1, String s2) {
if (s1 == null || s2 == null || s1.length() < 1 || s2.length() < 1) {
return 0;
}
return process(s1.toCharArray(), s2.toCharArray(), s1.length() - 1, s2.length() - 1);
}
// str1 从0....i
// str2 从0....j
// 最长公共子序列是多少
public static int process(char[] str1, char[] str2, int i, int j) {
if (i == 0 && j == 0) {
return str1[i] == str2[j] ? 1 : 0;
}
if (i == 0) {
if (str1[i] == str2[j]) {
return 1;
}
return process(str1, str2, i, j - 1);
}
if (j == 0) {
if (str1[i] == str2[j]) {
return 1;
}
return process(str1, str2, i - 1, j);
}
// 最长公共子序列不要i位置
int p1 = process(str1, str2, i - 1, j);
// 最长公共子序列不要j位置
int p2 = process(str1, str2, i, j - 1);
// 既要i位置，也要j位置(需要满足条件 str[i] == str[j])
// 既不要i位置，也不要j位置
int p3 = (str1[i] == str2[j] ? 1 : 0) + process(str1, str2, i - 1, j - 1);
return Math.max(p2, Math.max(p1, p3));
}
}
LeetCode 上直接超时
动态规划解
上述暴力递归过程有两个可变参数，可以定义一个二维数组
char[] str1 = s1.toCharArray();
char[] str2 = s2.toCharArray();
int[][] dp = new int[s1.length()][s2.length()];
其中dp[i][j]表示str1 从 0 开始一直到 i，str2 从 0 位置开始一直到 j，最长公共子序列是多少。
和暴力递归的递归函数表达的含义一样，基于暴力递归的 base case，可以得到二维数组 dp 的一些初始值
如果 i == 0 且 j == 0，说明 str1 和 str2 只有一个字符了，此时，如果str1[i] == str2[j] 则返回 1 ，表示最长公共子序列的长度就是 1， 否则则返回 0，表示最长公共子序列的长度就是 0，即
dp[0][0] = str1[0] == str2[0] ? 1 : 0;
如果 i == 0 且 j != 0，说明 str1 只有一个字符，而 str2 不止一个字符，此时如果str1[i] == str2[j]，说明最长公共子序列长度就是 1， 如果str1[i] != str2[j]，则让 i 继续去匹配 j - 1 位置，即:
for (int i = 1; i < s2.length(); i++) {
dp[0][i] = str1[0] == str2[i] ? 1 : dp[0][i - 1];
}
同理，如果 j == 0 且 i!= 0，说明 str2 只有一个字符，而 str1 不止一个字符，此时如果str1[i] == str2[j]，说明最长公共子序列长度就是 1， 如果str1[i] != str2[j]，则让 j 继续去匹配 i - 1 位置，即:
for (int i = 1; i < s1.length(); i++) {
dp[i][0] = str1[i] == str2[0] ? 1 : dp[i - 1][0];
}
接下来是普遍位置的情况，根据暴力递归的逻辑，也可以很方便求二维数组 dp 每个格子的依赖关系
for (int i = 1; i < str1.length; i++) {
for (int j = 1; j < str2.length; j++) {
int p1 = dp[i - 1][j];
// 最长公共子序列不要j位置
int p2 = dp[i][j - 1];
// 既要i位置，也要j位置(需要满足条件 str[i] == str[j])
// 既不要i位置，也不要j位置
int p3 = (str1[i] == str2[j] ? 1 : 0) + dp[i - 1][j - 1];
dp[i][j] = Math.max(p2, Math.max(p1, p3));
}
}
动态规划解完整代码如下
class Solution {
public static int longestCommonSubsequence(String s1, String s2) {
if (s1 == null || s2 == null || s1.length() < 1 || s2.length() < 1) {
return 0;
}
char[] str1 = s1.toCharArray();
char[] str2 = s2.toCharArray();
int[][] dp = new int[s1.length()][s2.length()];
dp[0][0] = str1[0] == str2[0] ? 1 : 0;
for (int i = 1; i < s2.length(); i++) {
dp[0][i] = str1[0] == str2[i] ? 1 : dp[0][i - 1];
}
for (int i = 1; i < s1.length(); i++) {
dp[i][0] = str1[i] == str2[0] ? 1 : dp[i - 1][0];
}
for (int i = 1; i < str1.length; i++) {
for (int j = 1; j < str2.length; j++) {
int p1 = dp[i - 1][j];
// 最长公共子序列不要j位置
int p2 = dp[i][j - 1];
// 既要i位置，也要j位置(需要满足条件 str[i] == str[j])
// 既不要i位置，也不要j位置
int p3 = (str1[i] == str2[j] ? 1 : 0) + dp[i - 1][j - 1];
dp[i][j] = Math.max(p2, Math.max(p1, p3));
}
}
return dp[s1.length() - 1][s2.length() - 1];
}
}