编辑距离算法

LeetCode-72-编辑距离, 以下代码均是根据此题的解法

编辑距离是什么?

答: 编辑距离指的是两个字符串相似程度, 即只允许修改/删除/增加一个字符, 需要多少次编辑操作才能将一个字符串转变为另外一个字符串.

回溯算法

当a[i]和b[i]不匹配时, 下一步的动作是有限的几种; 可以使用回溯算法遍历所有的情况.

当a[i]和b[i]匹配时, 直接考察i+1; 如果不匹配的话:

• 删除a[i], 递归a[i+1]和b[i]
• 删除b[i](增加一个等于b[i]的字符类似于删除), 递归a[i]和b[i+1]
• 将a[i]替换为b[i], 递归a[i+1]和b[i+1]

C++实现

class Solution {
    void core(const char *word1, const char *word2, int step, int &res)
    {
        if(!word1[0] && !word2[0])
        {
            res = min(res, step);
            return;
        }

        if(word1[0] == word2[0])
            core(word1+1, word2+1, step, res);
        else
        {
            if(*word1)
                core(word1+1, word2, step+1, res);
            if(*word2)
                core(word1, word2+1, step+1, res);
            if(*word1 && *word2)
                core(word1+1, word2+1, step+1, res);
        }
    }

public:
    int minDistance(string word1, string word2) {
        int res = INT_MAX;
        core(word1.c_str(), word2.c_str(), 0, res);
        return res;
    }
};

时间复杂度分析

  字符串长度为N, 每一级需要考虑3种情况, 时间复杂度达到了O(3^N)级别.

动态规划

如图: 可以看到存在重复的求解过程, 所以应当进行合并优化.

• 使用一个二维数组D记录i/j(两个字符串的索引)记录从这里到匹配结束需要的操作步数.

C++解法

class Solution {
    //返回剩余操作次数
    int core(const char *word1, const char *word2, int i, int j, int **f)
    {
        if(word1[i] && word2[j] && f[i][j] >= 0)
            return f[i][j];
        if(!word1[i] && !word2[j])
            return 0;
        if(word1[i] == word2[j])
            return (f[i][j] = core(word1, word2, i+1, j+1, f));
        else
        {
            int t = INT_MAX;
            if(word1[i])
                t = min(t, core(word1, word2, i+1, j, f));
            if(word2[j])
                t = min(t, core(word1, word2, i, j+1, f));
            if(word1[i] && word2[j])
                t = min(t, core(word1, word2, i+1, j+1, f));
            return (f[i][j] = t + 1);
        }
    }

public:
    int minDistance(string word1, string word2) {
        int len1 = word1.size();
        int len2 = word2.size();
        int **f = new int*[len1+1];
        int *buffer = new int[(len1+1)*(len2+1)];
        for(int i = 0; i <= len1; i++)
        {
            f[i] = buffer + (len2+1)*i;
            for(int j = 0; j <= len2; j++)
                f[i][j] = -1;
        }
        int res = core(word1.c_str(), word2.c_str(), 0, 0, f);
        delete []f;
        delete []buffer;
        return res;
    }
};

总结

• 1 回溯算法可以视作动态规划的粗暴解法
• 2 回溯算法的解题过程可以用一棵树来表示, 而动态规划就是进行剪枝.