dp2-minDistance.md

题目 给定两个单词 word1 和 word2，计算出将 word1 转换成 word2 所使用的最少操作数 。

你可以对一个单词进行如下三种操作：

插入一个字符

删除一个字符

替换一个字符

示例 1:

输入: word1 = "horse", word2 = "ros"

输出: 3

解释: horse -> rorse (将 'h' 替换为 'r')

rorse -> rose (删除 'r')

rose -> ros (删除 'e')

思路 动态规划，dp[i][j]代表word1的前i个字符转化成word2的前j个字符需要用的最少步骤。

从而可以推出dp[i][0] = i, dp[0][j] = j ，即插入n个字符。

如果word1[i-1] == word2[j-1] 则 dp[i][j] = dp[i-1][j-1] 也就是说当前的编辑距离和位置i和j的字符无关

如果word1[i-1] != word2[j-1] 有三种改变的方式

• word1插入一个元素，dp[i][j-1]+1
• word1删除一个元素，dp[i-1][j]+1
• word1改变一个元素，dp[i-1][j-1]+1

*代码

    class Solution {
public:
    int minDistance(string word1, string word2) {
        int m = word1.length(),n = word2.length();
        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;
        }
        int i,j;
        for(i=1;i<=m;i++) {
            for(j=1;j<=n;j++) {
                if(word1[i-1]==word2[j-1]) {
                    dp[i][j] = dp[i-1][j-1];
                }else{
                    dp[i][j] = min(dp[i-1][j-1],min(dp[i][j-1],dp[i-1][j]))+1;
                }
            
            }
        }
        return dp[m][n];
        
    }
};

参考链接

编辑距离