LeetCode 72. Edit Distance

Description

Given two words word1 and word2, find the minimum number of operations required to convert word1 to word2.
You have the following 3 operations permitted on a word:
Insert a character
Delete a character
Replace a character
Example 1:

Input: word1 = “horse”, word2 = “ros”
Output: 3
Explanation:
horse -> rorse (replace ‘h’ with ‘r’)
rorse -> rose (remove ‘r’)
rose -> ros (remove ’e’)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
>
> **Example 2:**
>
> ```
Input: word1 = "intention", word2 = "execution"
Output: 5
Explanation:
intention -> inention (remove 't')
inention -> enention (replace 'i' with 'e')
enention -> exention (replace 'n' with 'x')
exention -> exection (replace 'n' with 'c')
exection -> execution (insert 'u')

Solution

设最短距离方法为f：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
反推：

f("horse", "ros") = 1 + min(f("hors", "ros"), // 删除 hors[e]
                            f("horse", "ro"), // 插入 ro[s]
                            f("hors", "ro"))  // 替换 hors[e] ro[s]

f("hors", "ros") = 1 + min(f("hor", "ros"), // 删除 hor[s]
                           f("hors", "ro"), // 插入 ro[s]
                           f("hor", "ro"))  // 替换 hor[s] ro[s]
...

特殊情况和边界条件：
如果最后一个字符相同，则不用操作，distance = 0
如果其中一个字符串为空，则 distance = 另一个字符串长度

解释：

删除hors[e]：通过f("hors", "ros")将hors变成ros，则有rose删除最后一位得到ros
插入ro[s]：通过f("horse", "ro")将horse变成ro，则插入一位s得到ros
替换替换 hors[e] ro[s]：通过f("hors", "ro")将hors变成ro，则有roe替换最后一位得到ros

递归（Recursive）

 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
func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}
func min3(a, b, c int) int {
    return min(min(a, b), c)
}

func minDistance(word1, word2 string) int {
    w1, w2 := []byte(word1), []byte(word2)

    l1, l2 := len(w1), len(w2)

    cache := make([][]int, l1)
    for i := 0; i < l1; i++ {
        cache[i] = make([]int, l2)
    }

    var solve func(int, int) int
    solve = func(l1, l2 int) int {
        if l1 == 0 || l2 == 0 {
            return l1 + l2
        }

        idx1, idx2 := l1-1, l2-1

        if cache[idx1][idx2] >= 1 {
            // 缓存减一后返回
            return cache[idx1][idx2] - 1
        }

        var r int
        if w1[idx1] == w2[idx2] {
            // 末位相等
            r = solve(l1-1, l2-1)
        } else {

            r = 1 + min3(solve(l1-1, l2), // 删除
                solve(l1, l2-1),   // 插入
                solve(l1-1, l2-1)) // 替换
        }

        // 避免需要初始化成`-1`
        // 加一后缓存
        cache[idx1][idx2] = r + 1

        return r
    }

    return solve(l1, l2)
}

动态规划（Dynamic Programming）

 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
func minDistance(word1 string, word2 string) int {
    l1, l2 := len(word1), len(word2)

    if l1 == 0 || l2 == 0 {
        return l1 + l2
    }

    matrix := make([][]int, l1+1)
    for i := 0; i <= l1; i++ {
        matrix[i] = make([]int, l2+1)
        matrix[i][0] = i
    }
    for i := 0; i <= l2; i++ {
        matrix[0][i] = i
    }

    w1, w2 := []byte(word1), []byte(word2)
    for i := 1; i <= l1; i++ {
        for j := 1; j <= l2; j++ {
            if w1[i-1] == w2[j-1] {
                matrix[i][j] = matrix[i-1][j-1]
            } else {
                matrix[i][j] = 1 + min3(matrix[i-1][j-1],
                                matrix[i][j-1],
                                matrix[i-1][j])
            }
        }
    }

    return matrix[l1][l2]
}