72、编辑距离

leetcode

Created At : 2020-07-26 00:19

Count:640 Views 👀 :

Comment:

示例 1:
示例 2:

题解

动态规划

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

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

插入一个字符
删除一个字符
替换一个字符

示例 1:

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

解释:

horse -> rorse (将 ‘h’ 替换为 ‘r’)

rorse -> rose (删除 ‘r’)

rose -> ros (删除 ‘e’)

示例 2:

输入: word1 = "intention", word2 = "execution"
输出: 5

解释:

intention -> inention (删除 ‘t’)

inention -> enention (将 ‘i’ 替换为 ‘e’)

enention -> exention (将 ‘n’ 替换为 ‘x’)

exention -> exection (将 ‘n’ 替换为 ‘c’)

exection -> execution (插入 ‘u’)

题解

动态规划
- dp数组状态分析
- 枚举所用的情况

动态规划

用 d[i][j] 表示 A 的前 i 个字母和 B 的前 j 个字母之间的编辑距离。
对于A的 i 处的字符和B的j处的字符，有以下递推关系：
- 如果A[i] == B[i]，则：
  - $d[i][j] = min(d[i][j - 1]+1,d[i - 1][j] + 1,d[i - 1][j - 1]) = 1+min(d[i][j - 1],d[i - 1][j],d[i - 1][j - 1] - 1)$
- 如果A[i] != B[i]，则：
- $d[i][j] = 1 + min(d[i][j - 1],d[i - 1][j],d[i - 1][j - 1])$

public int minDistance(String word1,String word2){
    int n = word1.length();
    int m = word2.length();
    if (n*m == 0) {
        return n + m;
    } 
    int[][] d = new int[n + 1][m + 1];
    // 初始化
    for (int i = 0;i <= n;i++) {
        d[i][0] = i;
    }

    for (int j =0;j <= m;j++) {
        d[0][j] = j;
    }

    // 枚举所有情况，找到最优解
    for (int i = 1;i < n+1;i++){
        for (int j = 1;j < m+1;j++) {
            int left = d[i - 1][j] + 1;
            int down = d[i][j-1] + 1;
            int left_down =  d[i-1][j-1];
            if (word1.charAt(i - 1) != word2.charAt(j - 1)) {
                left_down += 1;
            }
            d[i][j] = Math.min(left, Math.min(down, left_down));
        }
    }

    return d[n][m];
}

最快代码——记忆化递归

class Solution {
    public int minDistance(String word1, String word2) {
        int l1 = word1.length();
        int l2 = word2.length();
        int[][] t = new int[l1+1][l2+1];
        for (int i = 1; i <= Math.min(l1, l2); i++) t[i][i] = -1;
        return wagner_fischer(word1, word2, l1, l2, t);
    }


    // 递归
    private int wagner_fischer(String w1, String w2, int i, int j, int[][] t) {
        if (i == 0) {
            return j;
        }
        if (j == 0) {
            return i;
        }
        if (i == j) {
            if (t[i][j] != -1) return t[i][j];
        } else {
            if (t[i][j] > 0) return t[i][j];
        }
        int d = 0;
        if (w1.charAt(i-1) == w2.charAt(j-1)) {
            d = wagner_fischer(w1, w2, i-1, j-1, t);
            t[i][j] = d;
            return d;
        }
        int d1 = wagner_fischer(w1, w2, i-1, j-1, t);
        int d2 = wagner_fischer(w1, w2, i-1, j, t);
        int d3 = wagner_fischer(w1, w2, i, j-1, t);
        d = Math.min(d1, d2);
        d = Math.min(d, d3) + 1;
        t[i][j] = d;
        return d;
    }
}

``

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1056615746@qq.com