Leetcode 编辑距离

这题之前面试遇到过一次，有一些细节的不了解，所以写一下我的理解好了

Y总的解答

定义

给定两个字符串 $A$ 和 $B$，编辑距离 $D(i, j)$ 表示将 $A$ 的前 $i$ 个字符转换为 $B$ 的前 $j$ 个字符所需的最少操作次数。

三种方式的对应

删除：$D(i-1, j) + 1$ 表示删除 $A[i]$。
插入：$D(i, j-1) + 1$ 表示在 $A$ 中插入 $B[j]$。
替换：$D(i-1, j-1) + 1$ 表示将 $A[i]$ 替换为 $B[j]$。

LC72 编辑距离

 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


func minDistance(word1 string, word2 string) int {
    m, n := len(word1), len(word2)	

    dp := make([][]int, m+1)
    for i := 0; i <= m; i++{
        dp[i] = make([]int, n+1)
        dp[i][0] = i 
    }
    for i := 0; i <= n; i++{
        dp[0][i] = i
    }

    for i := 1; i <= m; i++{
        for j := 1; j <= n; j++{
            if word1[i-1] == word2[j-1]{
                dp[i][j] = dp[i-1][j-1]
            }else{
                dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + 1
                dp[i][j] = min(dp[i][j], dp[i-1][j-1] + 1)
            }
        }
    }

    return dp[m][n]
}

LC221 最大正方形

我才意识到这题是编辑距离，dp[i][j]代表以(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


func maximalSquare(matrix [][]byte) int {
	
    // dp[i][j] 代表以 (i, j) 为右下角的最大边长
    row, col := len(matrix), len(matrix[0])
    dp := make([][]int, row)
    res := 0

    // 注意这里res不一定为0，也不一定为1
    for i := 0; i < row; i ++{
        dp[i] = make([]int, col)
        dp[i][0] = int(matrix[i][0] - '0')
        res = max(res, dp[i][0])
    }

    // 这里赋值这块得注意一下 byte 和 int
    for i := 0; i < col; i ++{
        dp[0][i] = int(matrix[0][i] - '0')
        res = max(res, dp[0][i])
    }

    // 原来 go 的 min 是支持多参数的啊
    for i := 1; i < row; i ++{
        for j := 1; j < col; j ++{
            if matrix[i][j] == '1'{
                dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
                res = max(res, dp[i][j])
            }
        }
    }

    return res * res
}