72. 编辑距离（困难）

Posted on Edited on In Views:

1，问题描述

72. 编辑距离

难度：中等（以前&现在都应该是困难才对）

给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数 。

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

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

示例 1：

1
2
3
4
5
6
输入：word1 = "horse", word2 = "ros"
输出：3
解释：
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')

示例 2：

1
2
3
4
5
6
7
8
输入：word1 = "intention", word2 = "execution"
输出：5
解释：
intention -> inention (删除 't')
inention -> enention (将 'i' 替换为 'e')
enention -> exention (将 'n' 替换为 'x')
exention -> exection (将 'n' 替换为 'c')
exection -> execution (插入 'u')

提示：

  • 0 <= word1.length, word2.length <= 500
  • word1 和 word2 由小写英文字母组成

2，思考过程

​ 嗯。。。没有一点思路！

​ 直接看解析吧

3，代码处理

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
import java.util.HashMap;
import java.util.Map;

public class _72编辑距离 {

    // 1纬数组动态规划没有搞懂
    public int minDistance_dynamic_single(String word1, String word2) {
        if (word1.equals(word2)) {
            return 0;
        }
        int m = word1.length(), n = word2.length();
        int[] dp = new int[n + 1];
        char[] chars1 = word1.toCharArray();
        char[] chars2 = word2.toCharArray();
        for (int i = 1; i <= n; i++) {
            dp[i] = i;
        }
        for (int i = 0; i < m; i++) {
            int pre = dp[0]++;
            for (int j = 0; j < n; j++) {
                int tmp = dp[j + 1];
                if (chars1[i] == chars2[j]) {
                    dp[j + 1] = pre;
                } else {
                    dp[j + 1] = Math.min(Math.min(dp[j + 1], dp[j]), pre) + 1;
                }
                pre = tmp;
            }
        }
        return dp[n];
    }

    // 动态规划的方法
    public int minDistance_dynamic(String word1, String word2) {
        int x = word1.length();
        int y = word2.length();
        int[][] dp = new int[x+1][y+1];// 存储单元
        for (int i = 0; i <= x; i++) {
            dp[i][0] = i;
        }
        for (int i = 0; i <= y; i++) {
            dp[0][i] = i;
        }

        for (int i = 0; i < word1.length(); i++) {
            for (int j = 0; j < word2.length(); j++) {
                if(word1.charAt(i) == word2.charAt(j)){
                    dp[i+1][j+1] = dp[i][j];
                }else {
                    dp[i+1][j+1] = Math.min(
                            Math.min(
                                    dp[i][j+1],
                                    dp[i+1][j]
                            ),
                            dp[i][j]
                    ) + 1;
                }
            }
        }
        return dp[x][y];
    }


    // 递归解决法（同时报错历史计算的数据，避免重复计算）
    public int minDistance(String word1, String word2) {
        String s1 = word1 + "-" + word2;
        if (map.containsKey(s1)) {
            return map.get(s1);
        }

        if (word1.isEmpty() || word2.isEmpty()) {
            // 必须要进行增加或者删除操作
            int max = Math.max(word1.length(), word2.length());
            map.put(s1, max);
            return max;
        }
        if (word1.charAt(0) == word2.charAt(0)) {
            // 首字母相同
            int sameInt = minDistance(word1.substring(1), word2.substring(1));
            map.put(s1, sameInt);
            return sameInt;
        }

        int min = Math.min(
                Math.min(
                        minDistance(word1.substring(1), word2),
                        minDistance(word1, word2.substring(1))
                ),
                minDistance(word1.substring(1), word2.substring(1))
        ) + 1;
        map.put(s1, min);
        return min;
    }

    private Map<String, Integer> map = new HashMap<>();


    public static void main(String[] args) {
        _72编辑距离 editDistance = new _72编辑距离();
//        System.out.println(editDistance.minDistance("horse", "ros"));
        System.out.println(editDistance.minDistance_dynamic("intention", "execution"));
    }

}

4，思考过程

​ 模式识别：一旦涉及子问题，可以用自上而下的递归和自下而上的动态规划问题

​ 可以使用递归与动态规划进行解决

​ 2维数组、1维数组的动态规划