[leetcode] Edit Distance

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

思路：

典型的动态规划题目。我是按照dp的解法来解的，初始化需要注意。假设word1的长度为a,word2的长度为b，那么需要开辟一个二维数组dp[a+1][b+1]，其中第一行代表一个空的word1通过添加变成word2所需的步骤，第一列代表word1通过删除变成word2的步骤。因此dp[i][0]=i;dp[0][j]=j.有关这个的具体的可以参考这篇博客。

题解：

class Solution {
public:
    int minDistance(string word1, string word2) {
        int len1 = word1.size();
        int len2 = word2.size();
        int **dp = new int *[len1+1];
        for(int i=0;i<=len1;i++)
            dp[i] = new int [len2+1];
        for(int i=0;i<=len1;i++)   //word1变成空的word2
            dp[i][0] = i;
        for(int j=0;j<=len2;j++)   //word2变成空的word1
            dp[0][j] = j;
        for(int i=1;i<=len1;i++)
            for(int j=1;j<=len2;j++)
            {
                if(word1[i-1]==word2[j-1])
                    dp[i][j] = dp[i-1][j-1];
                else {
                    dp[i][j] = min(min(dp[i-1][j], dp[i][j-1]), dp[i-1][j-1])+1;
                }
            }
        return dp[len1][len2];
    }
};