最長公共子序列問題
最長公共子序列問題
作者：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];
}
}
