72. Edit Distance

dp O(n²) time O(n) space rolling array

class Solution {
public:
    int minDistance(string word1, string word2) {
        int n = word1.length(), m = word2.length();
        vector<vector<int>> dp(2, vector<int>(m + 1));
        for (int i = 1; i <= m; ++i) {
            dp[0][i] = i; // 添加字符
        }
        for (int i = 1; i <= n; ++i) {
            int k = i & 1;
            dp[k][0] = i; // 删除字符
            for (int j = 1; j <= m; ++j) {
                if (word1[i - 1] == word2[j - 1]) {
                    dp[k][j] = dp[k ^ 1][j - 1];
                } else {
                    dp[k][j] = min({dp[k ^ 1][j - 1], dp[k][j - 1], dp[k ^ 1][j]}) + 1;
                }
            }
        }
        return dp[n & 1][m];
    }
};

dp O(n²) time O(n²) space
dp[i][j]表示word1[0:i]变成word2[0:j]最少需要多少步

class Solution {
public:
    int minDistance(string word1, string word2) {
        int n = word1.length(), m = word2.length();
        vector<vector<int>> dp(n + 1, vector<int>(m + 1));
        for (int i = 1; i <= m; ++i) {
            dp[0][i] = i;
        }
        for (int i = 1; i <= n; ++i) {
            dp[i][0] = i;
            for (int j = 1; j <= m; ++j) {
                if (word1[i - 1] == word2[j - 1]) { // 当两个字符相同时什么都不用做，dp[i - 1][j - 1] < dp[i][j - 1] + 1和dp[i - 1][j] + 1所以一定是dp[i - 1][j - 1]
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = min({dp[i - 1][j - 1], dp[i][j - 1], dp[i - 1][j]}) + 1;
                }
            }
        }
        return dp[n][m];
    }
};