题解 | #编辑距离(一)#

方法：动态规划

1、创建数组dp来存储，str1[i]到str[j]所需的最少操作数，可以得到如下的状态转移方程：

如果str1[i - 1]和str2[j - 1]相等时，dp[i][j] = dp[i - 1][j - 1]；

如果str1[i - 1]和str2[j - 1]不相等时，可能进行三种操作，取三种操作的最小值：

替换：dp[i - 1][j -1] + 1

删除：dp[i - 1][j] + 1，如果要满足删除可以从str1到str2，那么str1的前一个元素一定要满足转换到str2。所以是dp[i - 1][j] + 1。

插入：dp[i][j - 1] + 1，如果要满足插入可以从str1到str2，那么str1的当前元素一定要满足转换到str2的前一个元素为止，这样插入一个元素才能实现转换。所以是dp[i - 1][j] + 1。

2、最终的编辑距离就是数组dp的右下角元素。

时间复杂度：o(n*m)

空间复杂度：o(n*m)，n、m分别为两个字符串的长度。

class Solution {
  public:
    int editDistance(string str1, string str2) {
        // 特殊情况处理
        if (str1.length() == 0)
            return str2.length();
        if (str2.length() == 0)
            return str1.length();

        vector<vector<int> > dp(str1.length() + 1, vector<int> (str2.length() + 1, 0));
        // 初始化边界
        for (int i = 1; i <= str1.length(); i++)
            dp[i][0] = dp[i - 1][0] + 1;
        for (int i = 1; i <= str2.length(); i++)
            dp[0][i] = dp[0][i - 1] + 1;

        for (int i = 1; i <= str1.length(); i++) {
            for (int j = 1; j <= str2.length(); j++) {
                // 相等和不相等两种情况
                if (str1[i - 1] == str2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i][j - 1])) + 1;
                }
            }
        }

        return dp[str1.length()][str2.length()];
    }
};