72. 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[i][j]，表示word1第i个元素匹配word2第j个元素所需要删除，插入，修改的次数；
如果word1[i] == word2[j]，则表示两个字符是相同的，则dp[i][j] = dp[i-1][j-1]；
如果word1[i] ！= word2[j]，则表示两个字符是不相同的，则dp[i][j] = min( dp[i-1][j] + 1, min( dp[i][j-1] + 1, dp[i - 1][j - 1]))；

int minDistance(string word1, string word2) {
    int m = word1.size(), n = word2.size();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
    for (int i = 1; i <= m; i++)dp[i][0] = i;
    for (int j = 1; 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] = min(dp[i - 1][j - 1], min(dp[i - 1][j] + 1, dp[i][j - 1] + 1));
            else dp[i][j] = min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i][j - 1])) + 1;
        }
    }
    return dp[m][n];
}