算法-动态规划-编辑距离

算法-动态规划-编辑距离

1 题目概述

1.1 题目出处

https://leetcode.cn/problems/edit-distance/description/?envType=study-plan-v2&envId=top-interview-150

1.2 题目描述

2 动态规划

2.1 思路

dp[i][j] 表示 word1[0,i) 变换为 word2[0,j)的最少步数，那么转移表达式：

1. i和j上的字符相同时，则dp[i][j] = dp[i-1][j-1]，即这一步不需要做调整
2. i和j上的字符不同时，dp[i][j] = min(dp[i-1][j-1], dp[i][j-1], dp[i-1][j]) + 1，即当前要从i转移到j，有三种情况：
   1. i-1 j-1上的字符相同，那么直接现在把i字符替换为j即可
   2. i可以直接转为j-1，那么现在就增加一个j字符即可
   3. i-1可以直接转为j，那么现在就把i字符删除即可

2.2 代码

class Solution {
    public int minDistance(String word1, String word2) {
        // dp[i][j] 表示 word1[0,i) 变换为 word2[0,j)的最少步数

        int m = word1.length(), n = word2.length();
        int[][] dp = new int[m+1][n+1];

        // 初始化，word2长度为0时，word1的所有字符串删除来构成即可
        for (int i = 0; i <= m; i++) {
            dp[i][0] = i;
        }
        // 初始化，word1长度为0时，word2的所有字符串增加来构成即可
        for (int j = 0; j <= n; j++) {
            dp[0][j] = j;
        }

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; 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][j-1]), dp[i-1][j]) + 1;
                }
            }
        }

        return dp[m][n];
    }
}
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

2.3 时间复杂度

O(m * n)

2.4 空间复杂度

O(m * n)

3 DFS

3.1 思路

dp[i][j] 表示 word1[0,i) 变换为 word2[0,j)的最少步数，那么转移表达式：

1. i和j上的字符相同时，则dp[i][j] = dp[i-1][j-1]，即这一步不需要做调整
2. i和j上的字符不同时，dp[i][j] = min(dp[i-1][j-1], dp[i][j-1], dp[i-1][j]) + 1，即当前要从i转移到j，有三种情况：
   1. i-1 j-1上的字符相同，那么直接现在把i字符替换为j即可
   2. i可以直接转为j-1，那么现在就增加一个j字符即可
   3. i-1可以直接转为j，那么现在就把i字符删除即可

3.2 代码

class Solution {
    int[][] distances = null;
    public int minDistance(String word1, String word2) {
        distances = new int[word1.length()+1][word2.length()+1];
        for (int i = 0; i <= word1.length(); i++) {
            for (int j = 0; j <= word2.length(); j++) {
                distances[i][j] = -1;
            }
        }
        return dfs(word1, word2, 0, 0);
    }
    private int dfs(String word1, String word2, int i, int j) {
        if (distances[i][j] > -1) {
            return distances[i][j];
        }
        if (i == word1.length()) {
            // word1全增加
            distances[i][j] = word2.length() - j;
            return distances[i][j];
        }
        if (j == word2.length()) {
            // word1全删除
            distances[i][j] = word1.length() - i;
            return distances[i][j];
        }
        if (word1.charAt(i) == word2.charAt(j)) {
            // 当前字符相同，跳过，继续处理下一个
            distances[i][j] = dfs(word1, word2, i+1, j+1);
            return distances[i][j];
        }
        distances[i][j] = Math.min(Math.min(dfs(word1, word2, i, j+1), dfs(word1, word2, i+1, j)), dfs(word1, word2, i+1, j+1)) + 1;
        // 当前字符不同
        return distances[i][j];
    }
}
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

3.3 时间复杂度

O(m * n)

3.4 空间复杂度

O(m * n)

参考文档

• https://leetcode.cn/problems/edit-distance/solutions/763112/bao-li-dfs-ji-yi-you-hua-dfs-zhuang-tai-i9rut/?envType=study-plan-v2&envId=top-interview-150