Solving Word Search II: Finding Words on a Board

The "Word Search II" problem involves searching for all possible words from a given list within a grid of letters. This task requires efficiently traversing the grid and checking for the presence of words.

Problem Statement

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.

Example

Consider a board and a list of words:

Input:

Output:

Input:

Output:

Solution Approach - Trie and Backtracking

Breaking Down the Solution

• Trie for Word Storage: Store the list of words in a Trie for efficient searching.
• Backtracking for Grid Traversal: Use depth-first search (DFS) with backtracking to explore the board.
• Finding Words: On each step of DFS, check if the current path corresponds to a word in the Trie.

Conclusion

Word Search II is a challenging problem that combines Trie data structures with backtracking techniques, demonstrating advanced concepts in algorithm design and optimization.

Rust Solution

Rust's #[derive(Default)] gives TrieNode::default() for free, so TrieNode::new is a one-line wrapper and the leaf's word: Option<String> starts as None rather than TS's string | null. The entry(c).or_insert_with(TrieNode::new) call collapses the has/set/get insertion dance into a single lookup that hands back a &mut TrieNode to descend into. Marking a hit uses next.word.take().unwrap(), which swaps the Some out and leaves None behind in one move — the same "clear so it isn't reported twice" step the TS version does with = null. Because i/j are usize, the neighbour offsets go through i as isize + dx and back via x as usize so a -1 step can't underflow, and the whole board threads through as &mut Vec<Vec<char>> so the '#' marking is visible across the recursion.

Go Solution

Go keys the trie with map[byte]*TrieNode, so children are looked up by the raw w[i] byte and each node is reached through a *TrieNode pointer rather than a value. The comma-ok form next, ok := node.children[c] distinguishes a real child from a missing one, and an empty-string sentinel replaces TS's null: a leaf is next.word != "" and is cleared with next.word = "" to avoid re-reporting. Collecting a hit does *result = append(*result, next.word), dereferencing the shared *[]string accumulator, and the caller finishes with sort.Strings(found). Note that board [][]byte is passed by value yet the '#' marking still sticks, because the slice header shares its backing array across the recursion.