LeetCode·72.编辑距离·动态规划

链接：https://leetcode.cn/problems/edit-distance/solution/by-xun-ge-v-7g4m/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。 

题目

 

示例

 

思路

解题思路
动态规划
定义dp[i][j]数组表示word1中前 i 个字符 转换为 word2 中前 j 个字符所需要的步数

• 当 word1[i] == word2[j]时，我们不需要进行然后操作所以 dp[i][j] = dp[i-1][j-1]
• 当 word1[i] ！= word2[j]时，我们需要对当前位置进行调整，使得两个元素相等，存在三种调整方式
  • dp[i-1][j-1] 表示替换操作
  • dp[i-1][j] 表示删除操作
  • dp[i][j-1] 表示插入操作

我们取这三种方式中操作数最少的数更新为当前操作步数即可

内存优化
从上面思路来看，我们在计算当前位置操作数时，只需要用到dp[i-1][j] , dp[i][j-1] , dp[i-1][j-1]，分别为当前位置的上方，左边，左上角，那么我们可以将二维空间转换为一维，对于dp[i-1][j] -> 当前一维空间未更新之前的dp[j] , dp[i][j-1] -> 当前一维空间更新之后的dp[j-1], 那么dp[i-1][j-1]不好表示，我们申请一个变量临时保存他，然后动态更新即可

代码

动态规划内存优化

#define MIN(a , b , c) (((a) < (b) ? (a) : (b)) < (c) ? ((a) < (b) ? (a) : (b)) : (c))

int minDistance(char * word1, char * word2){
    int len1 = strlen(word1);
    int len2 = strlen(word2);
    int dp[len2+1];//初始化
    for(int i = 0; i < len2+1; i++)//初始化一维空间
    {
        dp[i] = i;
    }
    int s = dp[0];//临时变量保存dp【i-1】【j-1】
    for(int i = 0; i < len1; i++)
    {
        for(int j = 1; j <= len2; j++)
        {
            int t = dp[j];//动态更新保存dp[i-1][j-1]
            if(word1[i] == word2[j-1])
            {
                dp[j] = s;
            }
            else
            {
                dp[j] = MIN(dp[j] , dp[j-1] , s) + 1;
            }
            s = t;//更新dp[i-1][j-1]
        }
        dp[0]++;
        s = dp[0];
    }
    return dp[len2];
}


作者：xun-ge-v
链接：https://leetcode.cn/problems/edit-distance/solution/by-xun-ge-v-7g4m/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

动态规划

#define MIN(a , b , c) (((a) < (b) ? (a) : (b)) < (c) ? ((a) < (b) ? (a) : (b)) : (c))

int minDistance(char * word1, char * word2){
    int len1 = strlen(word1);
    int len2 = strlen(word2);
    int dp[len1+1][len2+1];
    for(int i = 0; i < len1+1; i++)
    {
        dp[i][0] = i;
    }
    for(int i = 0; i < len2+1; i++)
    {
        dp[0][i] = i;
    }
    for(int i = 1; i <= len1; i++)
    {
        for(int j = 1; j <= len2; j++)
        {
            if(word1[i-1] == word2[j-1])
            {
                dp[i][j] = dp[i-1][j-1];
            }
            else
            {
                dp[i][j] = MIN(dp[i-1][j] , dp[i][j-1] , dp[i-1][j-1]) + 1;
            }
        }
    }
    return dp[len1][len2];
}


作者：xun-ge-v
链接：https://leetcode.cn/problems/edit-distance/solution/by-xun-ge-v-7g4m/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。