Word search ii

Array String Backtracking Trie Matrix

38.1% acceptance

Jan 12, 2026

10128

506

Given an m x n board of characters and a list of strings words, return all words on the board. Each word must 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 in a word.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

struct WordSearchTrieNode {
  children: std::collections::HashMap<char, WordSearchTrieNode>,
  word: Option<String>,
}

impl Solution {
  pub fn find_words(board: Vec<Vec<char>>, words: Vec<String>) -> Vec<String> {
    let mut root = WordSearchTrieNode { children: std::collections::HashMap::new(), word: None };
    for word in words {
      let mut node = &mut root;
      for ch in word.chars() {
        node = node.children.entry(ch).or_insert(WordSearchTrieNode { children: std::collections::HashMap::new(), word: None });
      }
      node.word = Some(word);
    }
    
    let mut result = std::collections::HashSet::new();
    let m = board.len();
    let n = board[0].len();
    let mut board = board;
    
    for i in 0..m {
      for j in 0..n {
        Self::dfs(&mut board, i, j, &root, &mut result);
      }
    }
    result.into_iter().collect()
  }
  
  fn dfs(board: &mut Vec<Vec<char>>, i: usize, j: usize, node: &WordSearchTrieNode, result: &mut std::collections::HashSet<String>) {
    let ch = board[i][j];
    if ch == '#' || !node.children.contains_key(&ch) {
      return;
    }
    
    let next_node = &node.children[&ch];
    if let Some(word) = &next_node.word {
      result.insert(word.clone());
    }
    
    board[i][j] = '#';
    if i > 0 { Self::dfs(board, i - 1, j, next_node, result); }
    if j > 0 { Self::dfs(board, i, j - 1, next_node, result); }
    if i + 1 < board.len() { Self::dfs(board, i + 1, j, next_node, result); }
    if j + 1 < board[0].len() { Self::dfs(board, i, j + 1, next_node, result); }
    board[i][j] = ch;
  }
}