72. [✔][H]编辑距离
给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作：
- 插入一个字符
- 删除一个字符
- 替换一个字符
示例 1：
输入：word1 = "horse", word2 = "ros"
输出：3
解释：
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')
示例 2：
输入：word1 = "intention", word2 = "execution"
输出：5
解释：
intention -> inention (删除 't')
inention -> enention (将 'i' 替换为 'e')
enention -> exention (将 'n' 替换为 'x')
exention -> exection (将 'n' 替换为 'c')
exection -> execution (插入 'u')
提示：
0 <= word1.length, word2.length <= 500word1和word2由小写英文字母组成
题解：
/*
* @lc app=leetcode.cn id=72 lang=typescript
*
* [72] 编辑距离
*
* https://leetcode.cn/problems/edit-distance/description/
*
* algorithms
* Hard (62.82%)
* Likes: 2762
* Dislikes: 0
* Total Accepted: 334.3K
* Total Submissions: 532.1K
* Testcase Example: '"horse"\n"ros"'
*
* 给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数 。
*
* 你可以对一个单词进行如下三种操作：
*
*
* 插入一个字符
* 删除一个字符
* 替换一个字符
*
*
*
*
* 示例 1：
*
*
* 输入：word1 = "horse", word2 = "ros"
* 输出：3
* 解释：
* horse -> rorse (将 'h' 替换为 'r')
* rorse -> rose (删除 'r')
* rose -> ros (删除 'e')
*
*
* 示例 2：
*
*
* 输入：word1 = "intention", word2 = "execution"
* 输出：5
* 解释：
* intention -> inention (删除 't')
* inention -> enention (将 'i' 替换为 'e')
* enention -> exention (将 'n' 替换为 'x')
* exention -> exection (将 'n' 替换为 'c')
* exection -> execution (插入 'u')
*
*
*
*
* 提示：
*
*
* 0 <= word1.length, word2.length <= 500
* word1 和 word2 由小写英文字母组成
*
*
*/
// @lc code=start
function minDistance(word1: string, word2: string): number {
let m = word1.length;
let n = word2.length;
let memo = new Array(m).fill(1).map(() => new Array(n).fill(-1));
const dp = (s1: string, i: number, s2: string, j: number) => {
// 如果s1到头了，那么剩余步骤就是s2剩余的字符串长度，因为索引是j，长度就是j+1,也就是剩下的操作步数
if (i === -1) {
return j + 1;
}
if (j === -1) {
return i + 1;
}
if (memo[i][j] !== -1) {
return memo[i][j];
}
// 两个指针都往前走一步
if (s1[i] === s2[j]) {
memo[i][j] = dp(s1, i - 1, s2, j - 1);
} else {
memo[i][j] = Math.min(
// # 解释：
// # 我直接在 s1[i] 插入一个和 s2[j] 一样的字符
// 此时s1[i]后面的字符就是s2[j]，s1[i]是之前那个不一样的字符，不需要移动
// # 那么 s2[j] 就被匹配了，前移 j，继续跟 i 对比
// # 别忘了操作数加一
// https://labuladong.github.io/algo/images/editDistance/insert.gif
dp(s1, i, s2, j - 1) + 1,//插入
dp(s1, i - 1, s2, j) + 1,//删除
dp(s1, i - 1, s2, j - 1) + 1,//替换
)
}
return memo[i][j];
}
return dp(word1, m - 1, word2, n - 1);
};
// @lc code=end