1143. 最长公共子序列

**给定两个字符串 text1text2,返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ,返回0

一个字符串的 子序列 是指这样一个新的字符串:它是由原字符串在不改变字符的相对顺序的情况下删除某些字符(也可以不删除任何字符)后组成的新字符串。

  • 例如,“ace” 是 “abcde” 的子序列,但 “aec” 不是 “abcde” 的子序列。

  • 两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。

  • 示例 1:

    1
    2
    3
    输入:text1 = "abcde", text2 = "ace" 
    输出:3
    解释:最长公共子序列是 "ace" ,它的长度为 3
  • 示例 2:

    1
    2
    3
    输入:text1 = "abc", text2 = "abc"
    输出:3
    解释:最长公共子序列是 "abc" ,它的长度为 3
  • 示例 3:

    1
    2
    3
    输入:text1 = "abc", text2 = "def"
    输出:0
    解释:两个字符串没有公共子序列,返回 0
  • 提示:

    1. 1 <= text1.length, text2.length <= 1000
    2. text1 和 text2 仅由小写英文字符组成。

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
const longestCommonSubsequence = (text1, text2) => {
let dp = Array.from(Array(text1.length+1), () => Array(text2.length+1).fill(0));

for(let i = 1; i <= text1.length; i++) {
for(let j = 1; j <= text2.length; j++) {
if(text1[i-1] === text2[j-1]) {
dp[i][j] = dp[i-1][j-1] +1;;
} else {
dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1])
}
}
}

return dp[text1.length][text2.length];
};

583. 两个字符串的删除操作

给定两个单词 word1word2,找到使得 word1word2 相同所需的最小步数,每步可以删除任意一个字符串中的一个字符。

  • 示例:
1
2
3
输入: "sea", "eat"
输出: 2
解释: 第一步将"sea"变为"ea",第二步将"eat"变为"ea"
  • 提示:
  1. 给定单词的长度不超过500。
  2. 给定单词中的字符只含有小写字母。

题 解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 序列 DP
class Solution {
public int minDistance(String s1, String s2) {
char[] cs1 = s1.toCharArray(), cs2 = s2.toCharArray();
int n = s1.length(), m = s2.length();
int[][] f = new int[n + 1][m + 1];
for (int i = 0; i <= n; i++) f[i][0] = i;
for (int j = 0; j <= m; j++) f[0][j] = j;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
f[i][j] = Math.min(f[i - 1][j] + 1, f[i][j - 1] + 1);
if (cs1[i - 1] == cs2[j - 1]) f[i][j] = Math.min(f[i][j], f[i - 1][j - 1]);
}
}
return f[n][m];
}
}