华为72.编辑距离——动态规划（字符串操作典型题目）

题目描述

给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作：插入一个字符、删除一个字符、替换一个字符。
-示例 1：
-输入：word1 = "horse", word2 = "ros"
-输出：3
-解释：
-horse -> rorse (将 'h' 替换为 'r')
-rorse -> rose (删除 'r')
-rose -> ros (删除 'e')

思路

该题是字符串操作类用动态规划求解的典型题目，类似题目可以见第一篇博文。

1. 定义dp的含义——因为word1和word2分别对应两个状态，因此需要使用二维数组。
   dp[i][j]代表word1中前i个字符转变为word2中前j个字符所需要的最少操作数。
2. 状态转移方程
   题目***有三种操作方式：增、删、改，每种操作都对应一个转移方程。
   21、增加：当word1的前i个字符和word2的前j-1个字符已经相同后，只需要在word1后增加word2的最后一个字符即可，此时
   dp[i][j] = dp[i][j-1] + 1;
   22、删除：当word1的前i-1个字符和word2的前j个字符已经相同后，只需要将word1后删除一个字符即可，此时
   dp[i][j] = dp[i-1][j] + 1;
   33、修改：当word1的前i-1个字符和word2的前j-1个字符已经相同后，只需要修改word1最后一个字符和word2相同即可，此时
   dp[i][j] = dp[i-1][j-1] + 1;
   34、当word1的前i-1个字符和word2的前j-1个字符已经相同后，且word1第i个字符和word2第j个字符也相同，则不需要操作，此时
   dp[i][j] = dp[i-1][j-1];
   对于增、删、改三种操作是同一状态下的三种不同情况，因此要取三种情况中的最小值。
3. 边界条件
   当word1中字符为0时，转换为word2时，需要在word1中添加word2的单词个数，所以要初始化dp[0][i] = i;
   当word2中的字符为0时，要从word1转换为word2，需要将word1中字符都删除掉，所以要初始化dp[i][0] = i;

代码

class Solution {
public:
    int minDistance(string word1, string word2) {
        int len1 = word1.length(), len2 = word2.length();
        if(len1 == 0 || len2 == 0)
            return max(len1, len2);
        //初始化边界条件
        vector<vector<int>> dp(len1 + 1, vector<int>(len2 + 1, 0));
        for(int i = 0; i <= len1; i++)
            dp[i][0] = i;
        for(int i = 0; i <= len2; i++)
            dp[0][i] = i;
        //进行状态转移
        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(dp[i][j-1], min(dp[i-1][j], dp[i-1][j-1])) + 1;
            }
        }
        return dp[len1][len2];
    }
};