力扣编辑距离C++

### C++ 实现 LeetCode 编辑距离问题 编辑距离问题是动态规划的经典题目之一。以下是基于给定引用中的内容以及标准算法设计思路，提供一种完整的 C++ 解法。 #### 动态规划核心逻辑 定义 `dp[i][j]` 表示将字符串 `word1` 的前 `i` 个字符转换成 `word2` 的前 `j` 个字符所需的最小操作次数。状态转移方程如下： - 如果 `word1[i-1] == word2[j-1]`，则无需额外操作： \[ dp[i][j] = dp[i-1][j-1] \] - 否则，取以下三种情况的最小值并加一： - **替换**：`dp[i-1][j-1] + 1` - **删除**：`dp[i-1][j] + 1` - **插入**：`dp[i][j-1] + 1` 初始条件和边界条件为： - 当 `i=0` 或 `j=0` 时，表示其中一个字符串为空，则另一字符串的操作数等于其长度[^2]。 最终结果存储于 `dp[m][n]` 中，其中 `m` 和 `n` 分别是 `word1` 和 `word2` 的长度。 #### 完整代码实现 下面是该问题的标准 C++ 实现方式： ```cpp #include <vector> #include <string> using namespace std; class Solution { public: int minDistance(string word1, string word2) { int m = word1.length(), n = word2.length(); 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; // 填充 DP 表格 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] = min({dp[i - 1][j], // 删除 dp[i][j - 1], // 插入 dp[i - 1][j - 1]} // 替换 ) + 1; } } } return dp[m][n]; } }; ``` 上述代码通过二维数组 `dp` 存储中间计算结果，并逐步填充完成整个表格，最后返回右下角的结果作为答案[^3]。 #### 时间复杂度与空间复杂度分析 - **时间复杂度**：O(m * n)，其中 `m` 是 `word1` 的长度，`n` 是 `word2` 的长度。 - **空间复杂度**：O(m * n)，可以进一步优化到 O(min(m, n)) 使用滚动数组技术[^4]。 --- ###