LeetCode:Edit Distance

Given two words word1 and word2, find the minimum number of steps required to convert

word1 to word2. (each operation is counted as 1 step.)

You have the following 3 operations permitted on a word:

a) Insert a character

b) Delete a character

c) Replace a character

思路:

上述問題就是動態規劃中典型的字符串編輯距離問題.我們先來看下狀態的定義吧.

現假設原串為S，目標串為T，定義如下狀態:

dp[i+1][j+1]:表示S[0...i]與T[0....j]的最短編輯距離

那麼，我們可以得到如下的狀態的轉移方程:

dp[i+1][j+1] = min(dp[i][j+1]+1,min(dp[i][j]+(S[i]!=T[j]),dp[i+1][j]+1)).

下面解釋下狀態轉移方程是怎麼推導過程.

① 對於S[i]與T[0....j]來說,如果S[i]不在T[0....j]中,就表示S[i]被刪除了,所以dp[i+1][j+1] = dp[i][j+1] + 1.

②如果S[i]存在T[0....j]中，那麼，i可選的位置為0到j，剩下的k+1~j都可以看成是插入字符，所以可

得狀態轉移方程dp[i+1][j+1] = min(dp[i+1][k+1]+j-k),k∈[0,j].由於k=j時,情況較特殊,所以單獨討論k=j.

當k=j時,表示S[i]最終出現在T[j]這個位置,而這情況只有S[i]=T[j]或者S[i]!= T[j]兩種情況,如果

S[i]!=T[j],則表示此處進行了一次替換,所以有狀態轉移dp[i+1][j+1]=dp[i][j]+(S[i]!=T[j]).

而剩下的狀態為dp[i+1][j+1] = min(dp[i+1][k+1]+j-k),k∈[0,j)

現在面臨的關鍵就是怎麼將此狀態做到常數時間O(1).

證明:

令f(k) = dp[i+1][k+1] + j - k ，k∈[0,j),我們在k = i 處將此函數分段討論.

①

當0<=k<=i時,易知dp[i+1][k+1]是非遞增(由dp定義可知),而j-k是減函數.所以,當0<=k<=i時,f(k)遞減.

②

當i

而dp[i+1][i+1]+1=dp[i+1][i+2],即dp[i+1][i+1]+j-i=dp[i+1][i+2]+j-i-1,由此可知f(i)=f(i+1),

從而我們可以得到f(k)函數在其定義域上非遞增的，所以min(f(k)) =dp[i+1][j]+1，所以有狀態

dp[i+1][j+1] = dp[i+1][j] + 1.

下面是解題代碼:

class Solution {
public:
    int minDistance(string word1, string word2) 
    {
        int m = word1.size() , n = word2.size() ;
        int dp[m+1][n+1];
        for (int i = 0 ; i <= m ; ++i)
            dp[i][0] = i ;
        for (int j = 0 ; j <= n ; ++j)
            dp[0][j] = j ;
        for (int i = 0 ; i < m ; ++i)
            for (int j = 0 ; j < n ; ++j)
                dp[i+1][j+1] = min(dp[i][j+1]+1,min(dp[i+1][j]+1,dp[i][j] + ( word1[i] != word2[j] ) ) );
        return dp[m][n];
    }
};