https://leetcode.com/problems/word-search-ii/

word-search-ii.go

var directions = [4][2]int{
    {0, 1},
    {1, 0},
    {0, -1},
    {-1, 0},
}

func findWords(board [][]byte, words []string) []string {
    rows := len(board)
    
    if rows == 0 {
        return []string{}
    }
    
    cols := len(board[0])
    visited := make([][]bool, rows)
    
    for i, _ := range visited {
        visited[i] = make([]bool, cols)
    }
    
    result := []string{}
    
    for _, word := range words {
        found := false

        for i := 0; !found && i < rows; i++ {
            for j := 0; !found && j < cols; j++ {
                if board[i][j] == word[0] && hasWord(board, visited, i, j, word[1:]) {
                    found = true
                }
            }
        }
        
        if found {
            result = append(result, word)
        }
    }
    
    return result
}

func hasWord(board [][]byte, visited [][]bool, i, j int, word string) bool {
    if len(word) == 0 {
        return true
    }
    
    visited[i][j] = true
    
    defer func () {
        visited[i][j] = false
    }()
    
    for _, direction := range directions {
        x, y := i + direction[0], j + direction[1]
        
        if x < 0 || x >= len(board) || y < 0 || y >= len(board[0]) {
            continue
        }
        
        if visited[x][y] || board[x][y] != word[0] {
            continue
        }
        
        if hasWord(board, visited, x, y, word[1:]) {
            return true
        }
    }
    
    return false
}