Word search

Array String Backtracking Depth-First Search Matrix

46.9% acceptance

Jan 12, 2026

17558

753

Given an m x n grid of characters board and a string word, return true if word exists in the grid. The word can be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn exist(board: Vec<Vec<char>>, word: String) -> bool {
    let mut word = word.as_bytes().to_vec();
    let m = board.len();
    let n = board[0].len();
    let mut board = board;
    
    // Count character frequencies in board
    let mut board_freq = [0; 128];
    for i in 0..m {
      for j in 0..n {
        board_freq[board[i][j] as usize] += 1;
      }
    }
    
    // Early exit: check if word can exist in board
    let mut word_freq = [0; 128];
    for &ch in &word {
      word_freq[ch as usize] += 1;
      if word_freq[ch as usize] > board_freq[ch as usize] {
        return false;
      }
    }
    
    // Optimization: reverse word if last char is less frequent than first
    // This reduces the number of starting positions we need to explore
    if board_freq[word[0] as usize] > board_freq[word[word.len() - 1] as usize] {
      word.reverse();
    }
    
    for i in 0..m {
      for j in 0..n {
        if Self::dfs(&mut board, &word, i as i32, j as i32, 0, m as i32, n as i32) {
          return true;
        }
      }
    }
    false
  }
  
  fn dfs(board: &mut Vec<Vec<char>>, word: &[u8], i: i32, j: i32, idx: usize, m: i32, n: i32) -> bool {
    if i < 0 || j < 0 || i >= m || j >= n {
      return false;
    }
    
    let (ui, uj) = (i as usize, j as usize);
    if board[ui][uj] != word[idx] as char {
      return false;
    }
    
    if idx == word.len() - 1 {
      return true;
    }
    
    board[ui][uj] = '\0';
    
    let found = Self::dfs(board, word, i - 1, j, idx + 1, m, n) ||
          Self::dfs(board, word, i + 1, j, idx + 1, m, n) ||
          Self::dfs(board, word, i, j - 1, idx + 1, m, n) ||
          Self::dfs(board, word, i, j + 1, idx + 1, m, n);
    
    board[ui][uj] = word[idx] as char;
    found
  }
}