企业官网建设流程全解析

题目描述：

给你两个单词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')

解题思路：

方法一：动态规划

核心思路：

状态定义：

dp[i][j]= 将word1的前i个字符转换成word2的前j个字符所需的最少操作数。

状态转移：

对于word1[i-1]和word2[j-1]：

情况1：字符相同

dp[i][j] = dp[i-1][j-1] （不需要操作）

情况2：字符不同

dp[i][j] = 1 + min( dp[i-1][j], // 删除 word1[i-1] dp[i][j-1], // 插入 word2[j-1] dp[i-1][j-1] // 替换 word1[i-1] 为 word2[j-1] )

初始化：

• dp[0][j] = j：word1 为空，需要插入 j 个字符

• dp[i][0] = i：word2 为空，需要删除 i 个字符

具体过程示例：

word1 = "horse", word2 = "ros"

dp: "" r o s "" 0 1 2 3 h 1 1 2 3 o 2 2 1 2 r 3 2 2 2 s 4 3 3 2 e 5 4 4 3 dp[5][3] = 3 ✅

代码实现：

写法1：二维 DP

class Solution { public: int minDistance(string word1, string word2) { int m = word1.size(), n = word2.size(); vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0)); // 初始化 for (int i = 0; i <= m; i++) dp[i][0] = i; for (int j = 0; j <= n; j++) dp[0][j] = j; // 状态转移 for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { if (word1[i-1] == word2[j-1]) { dp[i][j] = dp[i-1][j-1]; } else { dp[i][j] = 1 + min({dp[i-1][j], dp[i][j-1], dp[i-1][j-1]}); } } } return dp[m][n]; } };

写法2：一维 DP（空间优化）

class Solution { public: int minDistance(string word1, string word2) { int m = word1.size(), n = word2.size(); vector<int> dp(n + 1, 0); // 初始化：word1 为空 for (int j = 0; j <= n; j++) dp[j] = j; for (int i = 1; i <= m; i++) { int prev = dp[0]; // 保存 dp[i-1][j-1] dp[0] = i; // dp[i][0] = i for (int j = 1; j <= n; j++) { int temp = dp[j]; // 保存 dp[i-1][j] if (word1[i-1] == word2[j-1]) { dp[j] = prev; } else { dp[j] = 1 + min({dp[j], dp[j-1], prev}); } prev = temp; // 更新 prev } } return dp[n]; } };

复杂度分析：

关键细节：

1. 三种操作对应哪些状态？

2. 为什么字符相同时不需要操作？

因为word1[i-1] == word2[j-1]，这两个字符已经匹配，只需要看前面的部分。

3. 一维 DP 的prev变量

prev保存的是dp[i-1][j-1]（左上角的值），因为dp[j-1]在当前行已经被更新了，不能直接用。

总结：