class Solution {
public:
int minDistance(string word1, string word2) {
}
};
583. 两个字符串的删除操作
给定两个单词 word1 和 word2 ，返回使得 word1 和 word2 相同所需的最小步数。
每步 可以删除任意一个字符串中的一个字符。
示例 1：
输入: word1 = "sea", word2 = "eat" 输出: 2 解释: 第一步将 "sea" 变为 "ea" ，第二步将 "eat "变为 "ea"
示例 2:
输入：word1 = "leetcode", word2 = "etco" 输出：4
提示：
1 <= word1.length, word2.length <= 500word1 和 word2 只包含小写英文字母原站题解
javascript 解法, 执行用时: 100 ms, 内存消耗: 48.2 MB, 提交时间: 2022-11-27 10:45:18
/**
* @param {string} word1
* @param {string} word2
* @return {number}
*/
var minDistance = function(word1, word2) {
const m = word1.length, n = word2.length;
const dp = new Array(m + 1).fill(0).map(() => new Array(n + 1).fill(0));
for (let i = 1; i <= m; i++) {
dp[i][0] = i;
}
for (let j = 1; j <= n; j++) {
dp[0][j] = j;
}
for (let i = 1; i <= m; i++) {
const c1 = word1[i - 1];
for (let j = 1; j <= n; j++) {
const c2 = word2[j - 1];
if (c1 === c2) {
dp[i][j] = dp[i - 1][j - 1];
} else {
dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + 1;
}
}
}
return dp[m][n];
};
golang 解法, 执行用时: 0 ms, 内存消耗: 6.5 MB, 提交时间: 2022-11-27 10:45:02
func minDistance(word1, word2 string) int {
m, n := len(word1), len(word2)
dp := make([][]int, m+1)
for i := range dp {
dp[i] = make([]int, n+1)
dp[i][0] = i
}
for j := range dp[0] {
dp[0][j] = j
}
for i, c1 := range word1 {
for j, c2 := range word2 {
if c1 == c2 {
dp[i+1][j+1] = dp[i][j]
} else {
dp[i+1][j+1] = min(dp[i][j+1], dp[i+1][j]) + 1
}
}
}
return dp[m][n]
}
func min(a, b int) int {
if a > b {
return b
}
return a
}
python3 解法, 执行用时: 232 ms, 内存消耗: 19 MB, 提交时间: 2022-11-27 10:44:46
'''
假设字符串 word1 和 word2 的长度分别为 m 和 n，创建 m+1 行 n+1 列的二维数组 dp，
其中 dp[i][j] 表示使 word1[0:i] 和 word2[0:j] 相同的最少删除操作次数。
上述表示中，word1[0:i] 表示 word1 的长度为 i 的前缀，word2[0:j] 表示 word2 的长度为 j 的前缀。
'''
class Solution:
def minDistance(self, word1: str, word2: str) -> int:
m, n = len(word1), len(word2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
dp[i][0] = i
for j in range(1, n + 1):
dp[0][j] = j
for i in range(1, m + 1):
for j in range(1, n + 1):
if word1[i - 1] == word2[j - 1]:
dp[i][j] = dp[i - 1][j - 1]
else:
dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + 1
return dp[m][n]
javascript 解法, 执行用时: 80 ms, 内存消耗: 47.7 MB, 提交时间: 2022-11-27 10:42:20
/**
* @param {string} word1
* @param {string} word2
* @return {number}
*/
var minDistance = function(word1, word2) {
const m = word1.length, n = word2.length;
const dp = new Array(m + 1).fill(0).map(() => new Array(n + 1).fill(0));
for (let i = 1; i <= m; i++) {
const c1 = word1[i - 1];
for (let j = 1; j <= n; j++) {
const c2 = word2[j - 1];
if (c1 === c2) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
const lcs = dp[m][n];
return m - lcs + n - lcs;
};
golang 解法, 执行用时: 4 ms, 内存消耗: 6.5 MB, 提交时间: 2022-11-27 10:42:04
func minDistance(word1, word2 string) int {
m, n := len(word1), len(word2)
dp := make([][]int, m+1)
for i := range dp {
dp[i] = make([]int, n+1)
}
for i, c1 := range word1 {
for j, c2 := range word2 {
if c1 == c2 {
dp[i+1][j+1] = dp[i][j] + 1
} else {
dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j])
}
}
}
lcs := dp[m][n]
return m + n - lcs*2
}
func max(a, b int) int {
if b > a {
return b
}
return a
}
python3 解法, 执行用时: 256 ms, 内存消耗: 17.2 MB, 提交时间: 2022-11-27 10:41:51
# 最长公共子序列
class Solution:
def minDistance(self, word1: str, word2: str) -> int:
m, n = len(word1), len(word2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
if word1[i - 1] == word2[j - 1]:
dp[i][j] = dp[i - 1][j - 1] + 1
else:
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
lcs = dp[m][n]
return m - lcs + n - lcs