leetcode72：编辑距离

题目链接

leetcode

题目描述

给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数。
你可以对一个单词进行如下三种操作：

插入一个字符
删除一个字符
替换一个字符

C++ 代码

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

/*
    状态表示：
        f[i][j] 表示将 A[1, i] 变成 B[1, j] 的最少操作次数
    状态计算：
        f[i][j] = min(操作1, 操作2, 操作3)
                = min(插入, 删除, 替换)
                = min(f[i-1][j] + 1,
                      f[i][j-1] + 1,
                      f[i-1][j-1] + 0 (A[i] == B[j]) 或 1 (A[i] != B[j]))

    时间复杂度：O(mn)
        其中 m 和 n 分别是两个字符串的长度。
    空间复杂度：O(mn)
        存储状态数组 f[i][j] 需要的空间为 O(mn)。
*/
class Solution {
public:
    int minDistance(string word1, string word2) {
        int m = word1.size(), n = word2.size();
        word1 = ' ' + word1, word2 = ' ' + word2;

        // f[i][j] 表示将 word1[1, i] 变为 word2[1, j] 的最少操作次数
        vector<vector<int>> f(m+1, vector<int>(n+1));
        // 状态初始化
        f[0][0] = 0;
        for (int i = 1; i <= m; i++) {
            f[i][0] = i; // 删除操作
        }
        for (int j = 1; j <= n; j++) {
            f[0][j] = j; // 插入操作
        }

        // 状态计算
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (word1[i] == word2[j]) {
                    f[i][j] = f[i-1][j-1];
                } else {
                    int insertCost = f[i-1][j] + 1;
                    int deleteCost = f[i][j-1] + 1;
                    int replaceCost = f[i-1][j-1] + 1;
                    f[i][j] = min(min(insertCost, deleteCost), replaceCost);
                }
            }
        }

        return f[m][n];
    }
};

/*
    优化空间

    时间复杂度：O(mn)
    空间复杂度：O(n)
*/
class Solution_1 {
public:
    int minDistance(string word1, string word2) {
        int m = word1.size(), n = word2.size();
        word1 = ' ' + word1, word2 = ' ' + word2;

        vector<int> f(n+1);
        for (int j = 0; j <= n; j++) {
            f[j] = j; // 初始化第一行：插入操作
        }

        // 状态计算
        for (int i = 1; i <= m; i++) {
            int prev = f[0]; // 保存左上角值（f[i-1][j-1]）
            f[0] = i; // 初始化第一列：删除操作

            for (int j = 1; j <= n; j++) {
                int temp = f[j]; // 当前位置旧值（会被覆盖）
                if (word1[i] == word2[j]) {
                    f[j] = prev;
                } else {
                    // 取插入、删除、替换的最小值 +1
                    f[j] = min({f[j-1], f[j], prev}) + 1;
                }
                prev = temp; // 更新 prev，准备下一次循环
            }
        }

        return f[n];
    }
};

int main() {
    Solution solution;
    vector<string> word1_cases = {
        "horse", "intention"
    };
    vector<string> word2_cases = {
        "ros", "execution"
    };

    for (int i = 0; i < word1_cases.size(); i++) {
        string word1 = word1_cases[i];
        string word2 = word2_cases[i];
        int result = solution.minDistance(word1, word2);

        cout << "Input: word1 = \"" << word1 
        << "\", word2 = \"" << word2 << "\"" << endl;
        cout << "Output: " << result << endl;
    }

    return 0;
}