LeetCode-Edit Distance

问题描述：
给定两个单词：word1以及word2，计算将word1转换成word2所需的最少操作数。

合法操作：

1. 插入一个字符；
2. 删除一个字符；
3. 替换一个字符。

解题思路：

动态规划：
dp[i][j]: word1[0,i-1]->word2[0][j-1]所需的最少操作

当word1[i] = word2[j]:
dp[i][j] = dp[i-1][j-1];

当word1[i] != word2[j]:
三种可能：
替换：
dp[i][j] = dp[i-1][j-1] + 1;
删除：
dp[i][j] = dp[i][j-1] + 1;
dp[i][j] = dp[i-1][j] + 1;

因此：dp[i][j] = min(dp[i-1][j-1],min(dp[i][j-1],dp[i-1][j])) + 1

class Solution {
public:
    int minDistance(string word1, string word2) {
        int len1 = word1.size();
        int len2 = word2.size();
        vector<vector<int>> dp;
        dp.resize(len1+1);
        for (int i=0;i<=len1;++i){
            dp[i].resize(len2+1,0);
        }
        for (int i=1;i<=word2.size();++i){
            dp[0][i] = i;
        }
        for (int i=1;i<=word1.size();++i){
            dp[i][0] = i;
        }
        for (int start=0;start<word1.size();++start){
            for (int end=0;end<word2.size();++end){
                if (word1[start] == word2[end]){
                    dp[start+1][end+1] = dp[start][end];
                    continue;
                }else{
                    dp[start+1][end+1] = min(dp[start][end],min(dp[start+1][end],dp[start][end+1]))+1;
                }
                
            }
        }
        return dp[len1][len2];
        
    }
};