Question

How to search for a word in a grid of characters with Go

Answer 1

// Use a depth‑first search (DFS) from every cell that matches the first letter,
// exploring all valid directions until the full word is matched.

package main

import (
    "fmt"
)

func dfs(grid [][]rune, visited [][]bool, r, c int, word string, index int) bool {
    if index == len(word) {
        return true
    }

    rows := len(grid)
    cols := len(grid[0])

    if r < 0 || c < 0 || r >= rows || c >= cols {
        return false
    }

    if visited[r][c] {
        return false
    }

    if grid[r][c] != rune(word[index]) {
        return false
    }

    visited[r][c] = true

    found :=
        dfs(grid, visited, r+1, c, word, index+1) ||
            dfs(grid, visited, r-1, c, word, index+1) ||
            dfs(grid, visited, r, c+1, word, index+1) ||
            dfs(grid, visited, r, c-1, word, index+1)

    visited[r][c] = false
    return found
}

func wordExist(grid [][]rune, word string) bool {
    rows := len(grid)
    cols := len(grid[0])

    visited := make([][]bool, rows)
    for i := range visited {
        visited[i] = make([]bool, cols)
    }

    for r := 0; r < rows; r++ {
        for c := 0; c < cols; c++ {
            if dfs(grid, visited, r, c, word, 0) {
                return true
            }
        }
    }

    return false
}

func main() {
    grid := [][]rune{
        {'a', 'b', 'c', 'e'},
        {'s', 'f', 'c', 's'},
        {'a', 'd', 'e', 'e'},
    }

    word := "see"

    result := wordExist(grid, word)
    if result {
        fmt.Println(1)
    } else {
        fmt.Println(0)
    }
}



/*
run:

1

*/

 

70+ SQL courses for beginners and professionals