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<k<j时,我们easy得知dp[i+1][k+1]+j-k是个常数,所以当i<k<j时,f(k)=dp[i+1][i+1+1]+j-i-1.

而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];
    }
};