龙

哇咔咔

0%

LeetCode 72 Edit Distance

发表于 更新于 分类于 Disqus：
Leetcode第72题，编辑距离问题。

Description:

Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.)

You have the following 3 operations permitted on a word:
a) Insert a character
b) Delete a character
c) Replace a character

题目理解，就是求将第一个字符串转化到第二个字符串所需要的最少步数，可以使用插入、删除、替换，三种策略。

这其实就是算法导论第15章，动态规划的思考题15-5，但是这道题会更加简单， 因为书上还有旋转操作。反正就是说这道题如果不使用动态规划，那么一定是过不了的。

思路一：先写一个递归算法，将它转化为自顶向上的动态规划。

思路二：自底向上。

代码一：

先考虑递归的情况，也就是取两个字符串的头字符$a_0$和$b_0$比较，然后按照：

  • $a_0$和$b_0$匹配，向下递归$a_1$和$b_1$。
  • $a_0$和$b_0$不匹配，
    • 使用replace，也就是将$a_0$替换为$b_0$，向下递归$a_1$和$b_1$。
    • 使用Insert，也就是在$a_0$前面插入$b_0$，向下递归$a_0$和$b_1$。
    • 使用Delete，也就是删除$a_0$，向下递归$a_1$和$b_0$。

上面的递归就可以求出少的操作次数，但是这样的递归将是指数复杂度的，所以更改其变为动态规划，减少子问题的重复计算。

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
class Solution {
    public int minDistance(String word1, String word2) {
        char[] a = word1.toCharArray(), b = word2.toCharArray();
        int m = a.length, n = b.length;
        int[][] dis = new int[m + 1][n + 1];
        for ( int i = 0; i < m; i++ )
            Arrays.fill(dis[i], -1);
        for ( int i = 0; i <= m; i++ )
            dis[i][n] = m - i;
        for ( int j = 0; j <= n; j++ )
            dis[m][j] = n - j;
        return myDis( a, b, 0, 0, dis );
    }

    private int myDis( char[] a, char[] b, int i, int j, int[][] dis ) {
        if ( dis[i][j] != -1 )
            return dis[i][j];
        if ( a[i] == b[j] ) {
            dis[i][j] = myDis( a, b, i + 1, j + 1, dis );
        } else {
            int dis1 = myDis( a, b, i, j + 1, dis );
            int dis2 = myDis( a, b, i + 1, j, dis );
            int dis3 = myDis( a, b, i + 1, j + 1, dis );
            int min = dis1 < dis2 ? dis1 : dis2;
            min = min < dis3 ? min : dis3;
            dis[i][j] = min + 1;
        }
        return dis[i][j];
    }
}

复杂度O(mn)。
运行时间8ms。
击败97.43%

image

代码二：

自底向上。

对照P223，定理15的定义法，先清晰一下思路。

令$a=(a_1,a_2,…,a_m)$和$b=(b_1,b_2,…,b_n)$两个序列，将第一个序列转化到第二个，那么：

  • 如果$a_m == b_n$，则次数等于$(a(m-1),b(n-1))$。
  • 如果$a_m \neq b_n$，则次数等于$(a(m-1),b(n-1))$与$(a(m),b(n-1))$与$(a(m-1),b(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
class Solution {
    public int minDistance(String word1, String word2) {
        char[] a = word1.toCharArray(), b = word2.toCharArray();
        int m = a.length, n = b.length;
        int[][] dis = new int[m + 1][n + 1];
        for ( int i = 0; i <= m; i++ )
            dis[i][0] = i;
        for ( int j = 0; j <= n; j++ )
            dis[0][j] = j;
        for ( int i = 1; i <= m; i++ ) {
            for ( int j = 1; j <= n; j++ ) {
                if ( a[i - 1] == b[j - 1] ) {
                    dis[i][j] = dis[i-1][j-1];
                } else if ( dis[i-1][j] > dis[i][j-1] ) {
                    if ( dis[i][j-1] > dis[i-1][j-1] )
                        dis[i][j] = dis[i-1][j-1] + 1;
                    else
                        dis[i][j] = dis[i][j-1] + 1;
                } else {
                    if ( dis[i-1][j] > dis[i-1][j-1] )
                        dis[i][j] = dis[i-1][j-1] + 1;
                    else
                        dis[i][j] = dis[i-1][j] + 1;
                }
            }
        }
        return dis[m][n];
    }  
}

复杂度O(mn)。
运行时间10ms。
击败92.12%

image

注：

自顶向上比自底向上快？？？想了一下，应该是因为在自顶向下的过程中，并不需要去将所有的子问题都计算出来。