Word Search

1. Problem Description

Given a two-dimensional grid and a word, determine whether the word exists in the grid.

The word must be formed in letter order using letters from adjacent cells, where adjacent cells are horizontally or vertically neighboring cells. The same cell may not be used more than once.

2. Approach

1. Approach 1
   • DFS, similar to Number of Islands. Is the reason memoization cannot be used here that this is brute-force enumeration?

3. Implementation

3.1. DFS

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

    // All elements need to be traversed here
    for i := range board {
        for j := range board[i] {
            if board[i][j] == word[0]{
                if existDFS(board, word, 0, i, j, len(board), len(board[0]), visited) {
                    return true
                }
            }
        }
    }
    return false
}


func existDFS(board [][]byte, word string, index, row, col, maxRow, maxCol int, visited [][]bool) bool {
    if index >= len(word) {return true}
    if row < 0 || row >= maxRow || col < 0 || col >= maxCol {return false}
    if visited[row][col] {return false}
    if word[index] == board[row][col] {
        visited[row][col] = true
        if isExists := existDFS(board, word, index+1, row+1, col, maxRow, maxCol, visited) ||
            existDFS(board, word, index+1, row-1, col, maxRow, maxCol, visited) ||
            existDFS(board, word, index+1, row, col+1, maxRow, maxCol, visited) ||
            existDFS(board, word, index+1, row, col-1, maxRow, maxCol, visited); isExists {
                return true
            }
        visited[row][col] = false
    }
    return false
}

4. References

• 79. Word Search - LeetCode