func (w *WordSearch) dfs(board [][]byte, word string, i, j int) bool {
	if len(word) == 0 {
		return true
	}
	if i < 0 ||
		i >= len(board) ||
		j < 0 ||
		j >= len(board[0]) ||
		board[i][j] != word[0] {
		return false
	}
	tmp := board[i][j]
	board[i][j] = '#'
	result := w.dfs(board, word[1:], i+1, j) ||
		w.dfs(board, word[1:], i-1, j) ||
		w.dfs(board, word[1:], i, j+1) ||
		w.dfs(board, word[1:], i, j-1)
	board[i][j] = tmp
	return result
}
dfs deep first search
package main
import (
	"fmt"
	"sort"
)
type WordSearch struct {
	board [][]byte
}
func (w *WordSearch) Exist(word string) bool {
	for i, h := range w.board {
		for j := range h {
			if w.dfs(w.board, word, i, j) == true {
				return true
			}
		}
	}
	return false
}