LeetCode 79. Word Search

Description

Given a 2D board and a word, find if the word exists in the grid.
The word can be constructed from letters of sequentially adjacent cell, where “adjacent” cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.
Example:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
board =
[
  ['A','B','C','E'],
  ['S','F','C','S'],
  ['A','D','E','E']
]

Given word = "ABCCED", return true.
Given word = "SEE", return true.
Given word = "ABCB", return false.

在board中查找是否存在相连（相邻）的字符与给定的单词对应。

很像一个走迷宫的题目，搜索下一步是否与单词的字母匹配，是则走到该位置。

Solution

 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
func exist(board [][]byte, word string) bool {
    height := len(board)
    if height == 0 {
        return false
    }

    width := len(board[0])
    if width == 0 {
        return false
    }

    w := []byte(word)
    wLength := len(w)

    var solve func(x, y, wordIndex int) bool
    solve = func(x, y, wordIndex int) bool {
        // 单词搜索完毕
        if wordIndex >= wLength {
            return true
        }

        // 边界检查
        if x >= width || x < 0 {
            return false
        }
        if y >= height || y < 0 {
            return false
        }

        // 检查当前格是否匹配
        if board[y][x] != w[wordIndex] {
            return false
        }

        // 修改当前格，避免重复搜索
        tmp := board[y][x]
        board[y][x] = byte(0)

        // 搜索下一格
        ok := solve(x-1, y, wordIndex+1) ||
            solve(x, y-1, wordIndex+1) ||
            solve(x+1, y, wordIndex+1) ||
            solve(x, y+1, wordIndex+1)

        // 还原当前格
        board[y][x] = tmp

        return ok
    }

    for i := 0; i < height; i++ {
        for j := 0; j < width; j++ {
            if solve(j, i, 0) {
                return true
            }
        }
    }

    return false
}