0079.单词搜索

https://leetcode.cn/problems/word-search/

方法一：回溯

时间复杂度 $O(mn \times 3^L)$，空间复杂度 $O(mn)$，其中 m 和 n 表示网格的长度与宽度 L 为字符串 word 的长度。

func exist(board [][]byte, word string) bool {
	visited, m, n := make([][]bool, len(board)), len(board), len(board[0])
	for i := 0; i < m; i++ {
		visited[i] = make([]bool, n)
	}
	var dfs func(x, y, idx int) bool
	dfs = func(x, y, idx int) bool {
		if board[x][y] != word[idx] {
			return false
		}
		if idx == len(word)-1 {
			return true
		}

		// judege top bottom left right
		dirx, diry := []int{-1, 1, 0, 0}, []int{0, 0, -1, 1}
		for i := 0; i < 4; i++ {
			j, k := x+dirx[i], y+diry[i]
			if j >= 0 && j < m && k >= 0 && k < n && !visited[j][k] {
				visited[j][k] = true
				if dfs(j, k, idx+1) {
					return true
				}
				visited[j][k] = false
			}
		}
		return false
	}
	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			if board[i][j] == word[0] {
				visited[i][j] = true
				if dfs(i, j, 0) {
					return true
				}
				visited[i][j] = false
			}
		}
	}
	return false
}