## Description

Word Search

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:

``````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 }``````