剑指 Offer 12. 矩阵中的路径

剑指 Offer 12. 矩阵中的路径

https://leetcode-cn.com/problems/ju-zhen-zhong-de-lu-jing-lcof/

第一版代码

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
var visited map[[2]int]bool
var target string

func exist(board [][]byte, word string) bool {
    visited = make(map[[2]int]bool)
    target = word
    for i := 0; i < len(board); i++ {
        for j := 0; j < len(board[0]); j++ {
            visited[[2]int{i, j}] = true
            if backtrack(board, i, j, "") {
                return true
            }
            delete(visited, [2]int{i, j})
        }
    }
    return false
}

func backtrack(board [][]byte, i, j int, track string) bool {
    m, n := len(board), len(board[0])

    if len(track) > len(target) {
        return false
    } 
    
    if len(track) == len(target) {
        if track == target {
            return true
        } else {
            return false
        }
    }

    if board[i][j] != target[len(track)] {
        return false
    }

    for _, pos := range getNextPos(i, j, m, n) {
        if _, ok := visited[pos]; !ok {
            visited[pos] = true
            if backtrack(board, pos[0], pos[1], track + string(board[i][j])) {
                return true
            }
            delete(visited, pos)
        }
    }
    
    // 加完当前字母后无路可走了
    return track + string(board[i][j]) == target
}

// 获取下一个合法位置
func getNextPos(i, j, m, n int) [][2]int {
    res := make([][2]int, 0)
    if i + 1 < m {
        res = append(res, [2]int{i+1, j})
    }
    if j + 1 < n {
        res = append(res, [2]int{i, j+1})
    }
    if i - 1 >= 0 {
        res = append(res, [2]int{i-1, j})
    }
    if j - 1 >= 0 {
        res = append(res, [2]int{i, j-1})
    }
    return res
}

改进

  1. 是否是合法位置可以进入函数后再判断 （i.e. 作为 base case）
  2. 是否访问过此位置也可以进入函数后判断，在继续 backtrack 之后、函数退出之前，释放对此位置的访问
  3. 由于每次进入函数只需要比较当前位置和 target 的某个值是否相等，不需要储存整个 track，只用记录当前匹配到哪里了
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
var visited map[[2]int]bool
var target string

func exist(board [][]byte, word string) bool {
    visited = make(map[[2]int]bool)
    target = word
    for i := 0; i < len(board); i++ {
        for j := 0; j < len(board[0]); j++ {
            if backtrack(board, i, j, 0) {
                return true
            }
        }
    }
    return false
}

func backtrack(board [][]byte, i, j, k int) bool {
    m, n := len(board), len(board[0])

    // 越界
    if i < 0 || i == m || j < 0 || j == n || board[i][j] != target[k] {
        return false
    }

    // 已访问过
    if _, ok := visited[[2]int{i, j}]; ok {
        return false
    }
    visited[[2]int{i, j}] = true

    // 已全部匹配
    if k == len(target) - 1 {
        return true
    }

    res := backtrack(board, i+1, j, k+1) || backtrack(board, i, j+1, k+1) || backtrack(board, i-1, j, k+1) || backtrack(board, i, j-1, k+1)
    
    delete(visited, [2]int{i, j})  // 退出节点，设为未访问
    return res
}