Question

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

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.

import Foundation

func dfs(
    _ grid: [[Character]],
    _ visited: inout [[Bool]],
    _ r: Int,
    _ c: Int,
    _ word: [Character],
    _ index: Int
) -> Bool {

    if index == word.count {
        return true
    }

    let rows = grid.count
    let cols = grid[0].count

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

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

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

    visited[r][c] = true

    let 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: [[Character]], _ word: String) -> Bool {
    let rows = grid.count
    let cols = grid[0].count

    var visited = Array(repeating: Array(repeating: false, count: cols), count: rows)
    let wordChars = Array(word)

    for r in 0..<rows {
        for c in 0..<cols {
            if dfs(grid, &visited, r, c, wordChars, 0) {
                return true
            }
        }
    }

    return false
}

func main() {
    let grid: [[Character]] = [
        ["a", "b", "c", "e"],
        ["s", "f", "c", "s"],
        ["a", "d", "e", "e"]
    ]

    let word = "see"

    let result = wordExist(grid, word)
    print(result ? 1 : 0)
}

main()


/*
run:

1

*/

 

70+ SQL courses for beginners and professionals