讓我們來看看編輯距離在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（體現(xiàn)在很多類似一次編輯的編程題中）停撞。其余幾種距離壤蚜，比如：Jaro distance，以后有機(jī)會(huì)繼續(xù)學(xué)習(xí)修然。

問題的開始：假定以當(dāng)作串a(chǎn)的前 個(gè)字符和串b的前 個(gè)字符的L氏編輯距離笛钝。

首先，是考慮初始值愕宋， 代表空串和前個(gè)字符玻靡，則對(duì)串a(chǎn)作次增或者對(duì)串b作次刪，即可完成串間轉(zhuǎn)換中贝，此時(shí)距離為囤捻。

其次，是對(duì)三種可能情況構(gòu)成（涵蓋增邻寿、刪蝎土、替換），取最小值：

1. (替換) 分別考慮前個(gè)字符绣否，那么當(dāng)前的和只需要看是否不相等誊涯，不相等就完成替換； 即：
2. (增/刪) 分別考慮前個(gè)字符蒜撮，分兩種情況：

• 2.1. 考慮從串a(chǎn)的個(gè)字符轉(zhuǎn)串b的字符暴构，此時(shí)，則相當(dāng)于是刪除了串a(chǎn)的第個(gè)字符，然后將串a(chǎn)剩余部分轉(zhuǎn)換成串b取逾；
• 2.2. 考慮從串b的個(gè)字符轉(zhuǎn)串a(chǎn)的個(gè)字符耗绿，此時(shí)，則相當(dāng)于在串b末尾增加了串a(chǎn)的第個(gè)字符砾隅，然后將原串b轉(zhuǎn)換成串a(chǎn)的前個(gè)字符误阻。
• 2.0. 以上兩種情況是對(duì)稱的形式，整合琉用，得堕绩。

3. (增/刪) 和第2點(diǎn)同理。整合邑时，得奴紧。

最終伊履，得到遞推公式：

根據(jù)遞推公式用押，就可以寫基礎(chǔ)版的程序：

此處以LeetCode的 面試題 01.05. 一次編輯 作為例子，僅供參考：

題目：字符串有三種編輯操作:插入一個(gè)字符彤路、刪除一個(gè)字符或者替換一個(gè)字符浅浮。 給定兩個(gè)字符串沫浆，編寫一個(gè)函數(shù)判定它們是否只需要一次(或者零次)編輯。

示例 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]();
        }
        // 空串情況(對(duì)應(yīng)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(對(duì)應(yīng)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;
    }
};

如何優(yōu)化滚秩？或者有其他更加巧妙的解法专执？希望不吝賜教。