题目
image.png
题解
题解1
超出时间限制
// dp[m,n]=dp[m-1,n-1]+1, s1[m]==s2[n]
// dp[m,n]=max(dp[m-1,n],dp[m,n-1]), s1[m]!=s2[n]
// base case
class Solution {
public int longestCommonSubsequence(String text1, String text2) {
if (text1.length() == 0 || text2.length() == 0) {
return 0;
}
int len1 = text1.length();
int len2 = text2.length();
return solver(text1, text2, len1 - 1, len2 - 1);
}
private int solver(String text1, String text2, int m, int n) {
if (m < 0 || n < 0) {
return 0;
}
if (text1.charAt(m) == text2.charAt(n)) {
return solver(text1, text2, m - 1, n - 1) + 1;
} else {
return Math.max(solver(text1, text2, m, n - 1), solver(text1, text2, m - 1, n));
}
}
}
题解2
对题解1的优化
// dp[m,n]=dp[m-1,n-1]+1, s1[m]==s2[n]
// dp[m,n]=max(dp[m-1,n],dp[m,n-1]), s1[m]!=s2[n]
// base case
class Solution {
private int[][] dp;
public int longestCommonSubsequence(String text1, String text2) {
if (text1.length() == 0 || text2.length() == 0) {
return 0;
}
int len1 = text1.length();
int len2 = text2.length();
dp = new int[len1][len2];
return solver(text1, text2, len1 - 1, len2 - 1);
}
private int solver(String text1, String text2, int m, int n) {
if (m < 0 || n < 0) {
return 0;
}
if (dp[m][n] != 0) { //
return dp[m][n];
}
if (text1.charAt(m) == text2.charAt(n)) {
// return solver(text1, text2, m - 1, n - 1) + 1;
dp[m][n] = solver(text1, text2, m - 1, n - 1) + 1;
} else {
// return Math.max(solver(text1, text2, m, n - 1), solver(text1, text2, m - 1, n));
dp[m][n] = Math.max(solver(text1, text2, m, n - 1), solver(text1, text2, m - 1, n));
}
return dp[m][n];
}
}
题解3
对题解2的dp优化
// dp[m,n]=dp[m-1,n-1]+1, s1[m]==s2[n]
// dp[m,n]=max(dp[m-1,n],dp[m,n-1]), s1[m]!=s2[n]
// base case
class Solution {
private int[][] dp;
public int longestCommonSubsequence(String text1, String text2) {
if (text1.length() == 0 || text2.length() == 0) {
return 0;
}
int len1 = text1.length();
int len2 = text2.length();
dp = new int[len1][len2];
// return solver(text1, text2, len1 - 1, len2 - 1);
if (text1.charAt(0) == text2.charAt(0)) {
dp[0][0] = 1;
} else {
dp[0][0] = 0;
}
for (int j = 1; j < len2; j++) { // dp[0][...]
if (text1.charAt(0) == text2.charAt(j)) {
dp[0][j] = 1;
} else {
dp[0][j] = Math.max(dp[0][j-1], 0);
}
}
for (int i = 1; i < len1; i++) { // dp[...][0]
if (text1.charAt(i) == text2.charAt(0)) {
dp[i][0] = 1;
} else {
dp[i][0] = Math.max(0, dp[i-1][0]);
}
}
for (int i = 1; i < len1; i++) {
for (int j = 1; j < len2; j++) {
if (text1.charAt(i) == text2.charAt(j)) {
dp[i][j] = dp[i-1][j-1] + 1;
} else {
dp[i][j] = Math.max(dp[i][j-1], dp[i-1][j]);
}
}
}
return dp[len1-1][len2-1];
}
}
题解4
对题解3的改造，因为0的处理太麻烦，所以索引+1，申请的长度也+1
特别是//3处的处理：
text1的索引是[0,i-1]，但是dp[i-1][...]代表的是[1,i-1]所以对应的text是[0,i-2]
dp[i][j] 的含义是：对于 s1[1..i] 和 s2[1..j]，它们的 LCS 长度是 dp[i][j]
// dp[m,n]=dp[m-1,n-1]+1, s1[m]==s2[n]
// dp[m,n]=max(dp[m-1,n],dp[m,n-1]), s1[m]!=s2[n]
// base case
class Solution {
private int[][] dp;
public int longestCommonSubsequence(String text1, String text2) {
if (text1.length() == 0 || text2.length() == 0) {
return 0;
}
int len1 = text1.length();
int len2 = text2.length();
dp = new int[len1 + 1][len2 + 1];
// return solver(text1, text2, len1 - 1, len2 - 1);
// if (text1.charAt(0) == text2.charAt(0)) {
// dp[0][0] = 1;
// } else {
// dp[0][0] = 0;
// }
// for (int j = 1; j < len2; j++) { // dp[0][...]
// if (text1.charAt(0) == text2.charAt(j)) {
// dp[0][j] = 1;
// } else {
// dp[0][j] = Math.max(dp[0][j-1], 0);
// }
// }
// for (int i = 1; i < len1; i++) { // dp[...][0]
// if (text1.charAt(i) == text2.charAt(0)) {
// dp[i][0] = 1;
// } else {
// dp[i][0] = Math.max(0, dp[i-1][0]);
// }
// }
for (int i = 1; i <= len1; i++) { // 1
for (int j = 1; j <= len2; j++) { // 2
if (text1.charAt(i-1) == text2.charAt(j-1)) { // 3
dp[i][j] = dp[i-1][j-1] + 1;
} else {
dp[i][j] = Math.max(dp[i][j-1], dp[i-1][j]);
}
}
}
return dp[len1][len2];
}
}
参考题解
class Solution {
public int longestCommonSubsequence(String text1, String text2) {
int m = text1.length();
int 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++){
if (text1.charAt(i-1)==text2.charAt(j-1)){
dp[i][j] = 1+dp[i-1][j-1];
}else{
dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
}
}
}
return dp[m][n];
}
}
和
def longestCommonSubsequence(str1, str2) -> int:
m, n = len(str1), len(str2)
# 构建 DP table 和 base case
dp = [[0] * (n + 1) for _ in range(m + 1)]
# 进行状态转移
for i in range(1, m + 1):
for j in range(1, n + 1):
if str1[i - 1] == str2[j - 1]:
# 找到一个 lcs 中的字符
dp[i][j] = 1 + dp[i-1][j-1]
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
return dp[-1][-1]
