题解 | #编辑距离(一)# 内存优化版本

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param str1 string字符串 
     * @param str2 string字符串 
     * @return int整型
     */
    int editDistance(string str1, string str2) {
        // write code here
        int n1 = str1.size();
        int n2 = str2.size();
        
        vector<int> dp(n2 + 1, 0);
        
        // 优化内存
        for(int i = 1; i <= n2; ++ i) dp[i] = i;
        for(int i = 1; i <= n1; ++ i)
        {
            int pre = dp[0];
            dp[0] = i;
            int temp;
            for(int j = 1; j <= n2; ++ j)
            {
                temp = dp[j];
                if(str1[i - 1] == str2[j - 1])
                {
                    dp[j] = pre; 
                }
                else
                { 
                    dp[j] = min(dp[j], min(pre, dp[j - 1])) + 1;
                }
                pre = temp;
            }
        }
        return dp[n2];
    }
};