编辑距离(DP)

让我们来看看编辑距离在WIKI是怎么说的：

There are other popular measures of edit distance, which are calculated using a different set of allowable edit operations. For instance,

• the Damerau–Levenshtein distance allows the transposition of two adjacent characters alongside insertion, deletion, substitution;
• the longest common subsequence (LCS) distance allows only insertion and deletion, not substitution;
• the Hamming distance allows only substitution, hence, it only applies to strings of the same length.
• the Jaro distance allows only transposition.

以上涵盖了多种编辑距离，但是允许的操作不一样，以增、删、替换为例，则需要使用Levenshtein distance（体现在很多类似一次编辑的编程题中）。其余几种距离，比如：Jaro distance，以后有机会继续学习。

---

问题的开始：假定以当作串a的前 个字符和串b的前 个字符的L氏编辑距离。

首先，是考虑初始值， 代表空串和前个字符，则对串a作次增或者对串b作次删，即可完成串间转换，此时距离为。

其次，是对三种可能情况构成（涵盖增、删、替换），取最小值：

1. (替换) 分别考虑前个字符，那么当前的和只需要看是否不相等，不相等就完成替换； 即：
2. (增/删) 分别考虑前个字符，分两种情况：

• 2.1. 考虑从串a的个字符转串b的字符，此时，则相当于是删除了串a的第个字符，然后将串a剩余部分转换成串b；
• 2.2. 考虑从串b的个字符转串a的个字符，此时，则相当于在串b末尾增加了串a的第个字符，然后将原串b转换成串a的前个字符。
• 2.0. 以上两种情况是对称的形式，整合，得。

3. (增/删) 和第2点同理。整合，得。

最终，得到递推公式：

根据递推公式，就可以写基础版的程序：

---

此处以LeetCode的 面试题 01.05. 一次编辑 作为例子，仅供参考：

题目：字符串有三种编辑操作:插入一个字符、删除一个字符或者替换一个字符。 给定两个字符串，编写一个函数判定它们是否只需要一次(或者零次)编辑。

示例 1:
输入:
first = "pale"
second = "ple"
输出: True
示例 2:
输入:
first = "pales"
second = "pal"
输出: False

class Solution {
public:
    bool oneEditAway(string first, string second) {
        // 建表
        int first_len = first.length();
        int second_len = second.length();
        int ** table = new int* [first_len+1];
        // 初始化
        for(int i = 0;i<= first_len; i++)
        {
            table[i] = new int[second_len+1]();
        }
        // 空串情况(对应1.)
        for(int i = 1;i<= first_len; i++)
        {
            table[i][0] = i;
        }
        for(int j = 1;j<= second_len;j++)
        {
            table[0][j] = j;
        }
        // 非空串的dp(对应2.和3.)
        for(int i = 1;i<= first_len; i++)
        {
            for(int j = 1;j<= second_len;j++)
            {
                int d1 = table[i-1][j-1];
                if (first[i-1] != second[j-1])
                {
                    d1 += 1;
                }
                int d2 = table[i-1][j] + 1;
                int d3 = table[i][j-1] + 1;
                table[i][j] = d1 > d2 ? (d3 > d2 ? d2 : d3) : (d3 > d1 ? d1 : d3);
            }   
        }

        return (table[first_len][second_len] <= 1) ? true : false;
    }
};

提交时间	提交结果	运行时间	内存消耗	语言
2 天前	通过	12 ms	8.6 MB	C++

---

如何优化？或者有其他更加巧妙的解法？希望不吝赐教。