Question

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

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.

fn dfs(
    grid: &Vec<Vec<char>>,
    visited: &mut Vec<Vec<bool>>,
    r: i32,
    c: i32,
    word: &Vec<char>,
    index: usize,
) -> bool {
    if index == word.len() {
        return true;
    }

    let rows = grid.len() as i32;
    let cols = grid[0].len() as i32;

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

    let rr = r as usize;
    let cc = c as usize;

    if visited[rr][cc] {
        return false;
    }

    if grid[rr][cc] != word[index] {
        return false;
    }

    visited[rr][cc] = 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[rr][cc] = false;
    found
}

fn word_exist(grid: Vec<Vec<char>>, word: &str) -> bool {
    let rows = grid.len();
    let cols = grid[0].len();

    let mut visited = vec![vec![false; cols]; rows];
    let word_chars: Vec<char> = word.chars().collect();

    for r in 0..rows {
        for c in 0..cols {
            if dfs(&grid, &mut visited, r as i32, c as i32, &word_chars, 0) {
                return true;
            }
        }
    }

    false
}

fn main() {
    let grid = vec![
        vec!['a', 'b', 'c', 'e'],
        vec!['s', 'f', 'c', 's'],
        vec!['a', 'd', 'e', 'e'],
    ];

    let word = "see";

    let result = word_exist(grid, word);
    println!("{}", if result { 1 } else { 0 });
}


/*
run:

1

*/

 

70+ SQL courses for beginners and professionals