题目描述
给你两个单词 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’)
思路&js代码
1、动态规划
🧩 状态定义：
我们用 dp[i][j] 表示将 word1[0..i-1]变为 word2[0..j-1] 的最小操作次数。
🔁 状态转移：
如果 word1[i-1] == word2[j-1]，不需要操作：dp[i][j] = dp[i-1][j-1]
否则，取三种操作中最小的一个 + 1：
插入：dp[i][j-1] + 1
删除：dp[i-1][j] + 1
替换：dp[i-1][j-1] + 1
🧱 初始化：
dp[i][0] = i：把前 i 个字符删光
dp[0][j] = j：把目标串插满
/**
* @param {string} word1
* @param {string} word2
* @return {number}
*/
var minDistance = function(word1, word2) {
const m = word1.length;
const n = word2.length;
// 初始化一个 (m+1) x (n+1) 的二维数组，默认值为0
const dp = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0));
// 初始化第一列：将 word1 前 i 个字符删除
for (let i = 0; i <= m; i++) {
dp[i][0] = i;
}
// 初始化第一行：将 word2 的前 j 个字符插入
for (let j = 0; j <= n; j++) {
dp[0][j] = j;
}
// 填表格，从 dp[1][1] 开始
for (let i = 1; i <= m; i++) {
for (let j = 1; j <= n; j++) {
// 默认取三种操作中的最小值 + 1
dp[i][j] = Math.min(
dp[i - 1][j - 1], // 替换
dp[i - 1][j], // 删除
dp[i][j - 1] // 插入
) + 1;
// 如果当前字符相等，就可以直接继承，不操作
if (word1[i - 1] === word2[j - 1]) {
dp[i][j] = Math.min(dp[i][j], dp[i - 1][j - 1]);
}
}
}
// 返回将 word1 转为 word2 的最小操作数
return dp[m][n];
};