编辑距离(一)

C++ 解法, 执行用时: 5ms, 内存消耗: 404KB, 提交时间: 2022-04-29

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

C++ 解法, 执行用时: 5ms, 内存消耗: 464KB, 提交时间: 2022-07-24

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param str1 string字符串 
     * @param str2 string字符串 
     * @return int整型
     */
    int editDistance(string str1, string str2) {
        // write code here
        int len1 = str1.size(), len2 = str2.size(), left_up;
//         vector<vector<int>> dp(len1 + 1, vector<int> (len2 + 1, 1001)); // dp[i][j] 表示str1从前i转换为str2从前j最少操作次数
        vector<int> dp(len2 + 1);
        for (int i = 0; i <= len2; ++i) {
            dp[i] = i;
        }
        for (int i = 1; i <= len1; ++i) {
            dp[0] = i;
            left_up = i - 1;
            for (int j = 1; j <= len2; ++j) {
                int up = dp[j];
                if (str1[i - 1] == str2[j - 1]) {
                    dp[j] = left_up;
                }
                else {
                    dp[j] = min({dp[j], dp[j - 1], left_up}) + 1;
                }
                left_up = up;
            }
        }
        return dp[len2];
    }
};

C++ 解法, 执行用时: 6ms, 内存消耗: 396KB, 提交时间: 2022-07-13

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

C++ 解法, 执行用时: 6ms, 内存消耗: 396KB, 提交时间: 2022-05-11

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];
    }
};

C++ 解法, 执行用时: 6ms, 内存消耗: 416KB, 提交时间: 2022-07-09

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param str1 string字符串 
     * @param str2 string字符串 
     * @return int整型
     */
    int editDistance(string str1, string str2) {
        // write code here
        //dp[i][j] 表示str1以i结尾，str2以j结尾时需要操作的次数
//         int n1 = str1.length();
//         int n2 = str2.length();
//         vector<vector<int>> dp(n1+1, vector<int>(n2+1,0));
//         for(int i = 1; i <= n1; i++){
//             dp[i][0] = dp[i-1][0]+1;
//         }
//         for(int j = 1; j <= n2; ++j){
//             dp[0][j] = dp[0][j-1] +1;
//         }
        
//         for(int i = 1; i <= n1; ++i){
//             for(int j = 1; j <= n2; ++j){
//                 if(str1[i-1] == str2[j-1]){
//                     dp[i][j] = dp[i-1][j-1];
//                 }else{
//                     dp[i][j] = min(dp[i-1][j-1] , min(dp[i-1][j], dp[i][j-1])) + 1;
//                 }
//             }
//         }
//         return dp[n1][n2];
        //内存优化
        int n1 = str1.length();
        int n2 = str2.length();
        if(n1 == 0) return n2;
        if(n2 == 0) return n1;
        int dp[2][n2+1];
        dp[0][0] = 0;
//         vector<vector<int>> dp(2, vector<int>(n2+1, 0));
        for(int j = 1; j <= n2; ++j){
            //当str1为空时，需要添加str2，操作次数为str2的长度
            dp[0][j] = j; 
        }
        for(int i = 1; i <= n1; ++i){
            //当str2为空时，str1需要删除自身，操作次数为str1的长度
            dp[i % 2][0] = i;
            for(int j = 1; j <= n2; ++j){
                //当前字符相等时，不需要操作
                if(str1[i-1] == str2[j-1]){
                    dp[i%2][j] = dp[(i-1)%2][j-1];
                }else{
                    //当前字符不相等时就看是换，还是添加，还是删除操作数少
                    dp[i%2][j] = min(dp[(i-1)%2][j-1], min(dp[(i-1)%2][j], dp[i%2][j-1])) + 1;
                }
            }
        }
        return dp[n1%2][n2];
    }
};

详情