Leetcode 72. Edit Distance

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

You have the following 3 operations permitted on a word:

Insert a character
Delete a character
Replace a character
Example 1:

Input: word1 = “horse”, word2 = “ros”
Output: 3
Explanation:
horse -> rorse (replace ‘h’ with ‘r’)
rorse -> rose (remove ‘r’)
rose -> ros (remove ‘e’)
Example 2:

Input: word1 = “intention”, word2 = “execution”
Output: 5
Explanation:
intention -> inention (remove ‘t’)
inention -> enention (replace ‘i’ with ‘e’)
enention -> exention (replace ‘n’ with ‘x’)
exention -> exection (replace ‘n’ with ‘c’)
exection -> execution (insert ‘u’)
解析：
计算从word1到word2进行转换的次数，包括增加一个字符、删除一个字符和替换一个字符。
采用动态规划来做，定义dp[i][j]表示从word1的i位置转换到word2的j位置的编辑距离。
然后来看动态规划的递推公式。
如果word1[i]==word2[j],则编辑距离不变，即dp[i][j] == dp[i-1][j-1]
如果word1[i]!=word2[j],则现在需要进行转换操作，
a.删除
如果将word1[i]删除，则此时
dp[i][j] = dp[i-1][j] + 1
b.增加
如果在word1[i]之后插入word2[j],即相当于删除word2[j],则此时
dp[i][j] = dp[i][j-1] + 1。
c.替换
将word1[i]替换为word2[j]
dp[i][j] = dp[i-1][j-1] + 1
另外需要处理word1或者wrod2为空的情况。
具体代码如下：

class Solution {
public:
    int minDistance(string word1, string word2) {
        int m = word1.size();
        int n = word2.size();
        vector<vector<int>> dp(m+1, vector<int>(n+1));
        //处理word2为空的情况，此时ED即为word1长度
        for(int i=0; i <= m; i++)
            dp[i][0] = i;
        //处理word1为空的情况
        for(int j =0; j <=n; j++)
            dp[0][j] = j;
        for(int i=1; i<= m; i++)
            for(int j=1; j <= n; j++)
            {
                if(word1[i-1] == word2[j-1])
                    dp[i][j] = dp[i-1][j-1];
                else
                {
                    dp[i][j] = min(dp[i-1][j], min(dp[i][j-1], dp[i-1][j-1])) + 1;
                }
            }
        return dp[m][n];
    }
};

</vector