题解 | 编辑距离(一)

class Solution {
  public:
        int editDistance(string str1, string str2) {
        // 确保str1是较短的字符串，减少空间使用
        if (str1.length() > str2.length())
            swap(str1, str2);
            
        int m = str1.length();
        int n = str2.length();
        
        // 只使用一个一维数组，空间复杂度O(min(m,n))
        vector<int> dp(m + 1);
        for (int i = 0; i <= m; i++)
            dp[i] = i;
        
        // 填充DP表格
        for (int j = 1; j <= n; j++) {
            int prev = dp[0]; // 保存dp[i-1][j-1]的值
            dp[0] = j;        // 第一列的初始化
            
            for (int i = 1; i <= m; i++) {
                int temp = dp[i]; // 暂存当前dp[i]的值，用于下一个位置的计算
                
                if (str1[i-1] == str2[j-1])
                    dp[i] = prev;
                else
                    dp[i] = 1 + min({dp[i],    // 删除
                                    dp[i-1],   // 插入
                                    prev});    // 替换
                                    
                prev = temp; // 更新prev为当前位置的原值
            }
        }
        
        return dp[m];
    }
};