79.M 单词搜索

Problem: 79. 单词搜索

思路

回溯法。

定义backtrack方法用于检查以[i, j]位置为起点能够在网格中找到字符串word[start:]，该方法的主要逻辑是：

1. 如果start到达word结尾的位置，则匹配成功

2. 如果[i, j]超出网格，则匹配失败

3. 如果当前字符已访问过，则匹配失败

4. 如果当前字符不等于word[start]，则匹配失败

5. 标记当前字符为已访问过

6. 检查上下左右的网格，只要有一个匹配成功，则整个方法返回匹配成功。

需要注意的是，需要检查以棋盘每个位置为起点的检查结果，只要有一个成功，即为成功。

Code

func exist(board [][]byte, word string) bool {
	visited := make([][]bool, len(board))
	for i := 0; i < len(visited); i++ {
		visited[i] = make([]bool, len(board[0]))
	}

	for i, row := range board {
		for j := range row {
			if backtrack(board, i, j, word, 0, visited) {
				return true
			}
		}
	}

	return false
}

func backtrack(board [][]byte, i int, j int, word string, start int, visited [][]bool) bool {
	if start == len(word) {
		return true
	}

	if i < 0 || i >= len(board) || j < 0 || j >= len(board[0]) {
		return false
	}

	if visited[i][j] {
		return false
	}

	if board[i][j] != word[start] {
		return false
	}

	visited[i][j] = true
	ans := backtrack(board, i+1, j, word, start+1, visited) ||
		backtrack(board, i, j+1, word, start+1, visited) ||
		backtrack(board, i-1, j, word, start+1, visited) ||
		backtrack(board, i, j-1, word, start+1, visited)
	visited[i][j] = false
	return ans
}