题解 | #编辑距离(一)#

#include <vector>
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param str1 string字符串
     * @param str2 string字符串
     * @return int整型
     */
    // 记忆化搜索
    // int editDistance(string str1, string str2) {
    //     // write code here
    //     int n=str1.size(),m=str2.size();
    //     vector<vector<int>> memo(n+1,vector<int>(m+1,-1));
    //     function<int(int,int)> dfs =[&](int i,int j) ->int  {
    //         if(i<0) return j+1;//由于一个字符串为空，所以返回你要把这j+1个字符都删掉
    //         if(j<0) return i+1;//由于一个字符串为空，所以返回你要把这i+1个字符都删掉
    //         int &res=memo[i][j];
    //         if(res!=-1) return res;
    //         if(str1[i]==str2[j]) return res=dfs(i-1,j-1);
    //         return res=min(min(dfs(i-1,j),dfs(i,j-1)),dfs(i-1,j-1))+1;
    //     };
    //     return dfs(n-1,m-1);
    // }
    // 记忆化搜索改成动态规划
    // int editDistance(string str1, string str2) {
    //     // write code here
    //     int n = str1.size(), m = str2.size();
    //     vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
    //     for (int j = 0; j <= m; j++) dp[0][j] = j;
    //     for (int i = 0; i <= n; i++) dp[i][0] = i;
    //     for (int i = 0; i < n; i++) {
    //         for (int j = 0; j < m; j++) {
    //             if (str1[i] == str2[j]) dp[i + 1][j + 1] = dp[i][j];
    //             else dp[i + 1][j + 1] = min(min(dp[i][j + 1], dp[i + 1][j]), dp[i][j]) + 1;
    //         }
    //     }
    //     return dp[n][m];
    // }
    // 二维dp 优化空间
    // int editDistance(string str1, string str2) {
    //     // write code here
    //     int n = str1.size(), m = str2.size();
    //     vector<vector<int>> dp(2, vector<int>(m+1, 0));
    //     for (int j = 0; j <= m; j++) dp[0][j] = j;
    //     for (int i = 0; i < n; i++) {
    //         dp[(i + 1) % 2][0] = i + 1;
    //         for (int j = 0; j < m; j++) {
    //             if (str1[i] == str2[j]) dp[(i + 1)%2][j + 1] = dp[i%2][j];
    //             else dp[(i + 1)%2][j + 1] = min(min(dp[i%2][j + 1], dp[(i + 1)%2][j]), dp[i%2][j]) + 1;
    //         }
    //     }
    //     return dp[n%2][m];
    // }
    // 一维dp 优化空间
    int editDistance(string str1, string str2) {
        // write code here
        int n = str1.size(), m = str2.size();
        vector<int> dp(m+1, 0);
        for (int j = 0; j <= m; j++) dp[j] = j;
        for (int i = 0; i < n; i++) {
            int pre=dp[0];
            dp[0] = i + 1;
            for (int j = 0; j < m; j++) {
                int tmp = dp[j+1];
                if (str1[i] == str2[j]) dp[j + 1] = pre;
                else dp[j + 1] = min(min(dp[j + 1], dp[j]), pre) + 1;
                pre = tmp;
            }
        }
        return dp[m];
    }
};


// dfs(i,j)

// ① str1[i]==str2[j]  return dfs(i-1,j-1);

// ② str1[i]!=str2[j]
// dfs(i-1,j)+1
// dfs(i,j-1)+1
// dfs(i-1,j-1)+1
// return min(min(dfs(i-1,j),dfs(i,j-1)),dfs(i-1,j-1))+1;


// dfs(i,j) = min(min(dfs(i-1,j),dfs(i,j-1)),dfs(i-1,j-1))+1;

// dfs(i+1,j+1) = min(min(dfs(i,j+1),dfs(i+1,j)),dfs(i,j))+1;