LeetCode——编辑距离

NO.72 编辑距离困难

思路一：动态规划 从递归到从顶向下记忆化再到从底向上的逐步优化过程记不记录了。直接给出最终的方法。

dp[i][j]的含义：word1的[0,i]子串和word2的[0,j]子串之间最少的编辑次数。

初始化：大小是[word1Length+1][word2Length+1]，包含两个字符串的空子串。dp[0][0]不需要编辑即为0。第一列dp[i][0]表示word2是空，即word1每个字符都需要执行删除操作进行编辑。第一行dp[0][j]表示word1是空，即word1每次只需要对应word2的字符进行插入操作进行编辑。

状态转移：dp[i][j]如果word1的i元素和word2的j元素相等，则不需要编辑，所以编辑距离等于dp[i-1][j-1]的编辑距离；否则i元素和j元素不不相等，则可以进行替换、删除、插入操作，即替换dp[i-1][j-1]、删除dp[i-1][j]、插入[i][j-1]，选择编辑距离最小的方式即可。

public int minDistance(String word1, String word2) {
    int len1 = word1.length(), len2 = word2.length();
    int[][] dp = new int[len1 + 1][len2 + 1];
    //初始化
    for (int i = 1; i <= len1; i++) {
        dp[i][0] = dp[i - 1][0] + 1;
    }
    for (int j = 1; j <= len2; j++) {
        dp[0][j] = dp[0][j - 1] + 1;
    }
    //状态转移
    for (int i = 1; i <= len1; i++) {
        for (int j = 1; j <= len2; j++) {
            if (word1.charAt(i - 1) == word2.charAt(j - 1)) dp[i][j] = dp[i - 1][j - 1];
            else dp[i][j] = Math.min(Math.min(dp[i - 1][j - 1], dp[i - 1][j]), dp[i][j - 1]) + 1;
        }
    }
    return dp[len1][len2];
}

时间复杂度：O(len1*len2)

本人菜鸟，有错误请告知，感激不尽！

更多题解和源码:github

NO.72 编辑距离 困难

NO.72 编辑距离困难