Start learning free

LESSON 434 OF 543 · TRIES

Word Search II in Rust: Trie and Backtracking, O(R·C·4^L)

Practice O(R · C · 4L) Read the full explanation

Given a grid of letters board with R rows and C columns, and an array of strings words, return every word of words that can be traced on the board.

A word is traced by a path of cells: its first letter is in some cell, and each next letter is in a cell next to the previous one, horizontally or vertically (not diagonally). A cell can be used only once in the same word.

Return each word found once, in any order: the output lists the words in alphabetical order. If no word can be traced, the answer is empty.

 

Example 1:

Input: board = [
  ["o", "a", "a", "n"],
  ["e", "t", "a", "e"],
  ["i", "h", "k", "r"],
  ["i", "f", "l", "v"]
], words = ["oath", "pea", "eat", "rain"]
Output: ["eat", "oath"]
Explanation: "oath" starts at the top-left "o", goes right to "a", down to "t" and down again to "h".
"eat" starts at the "e" at the right end of the second row, then goes left to "a" and left again to "t".
The board has no "p", so "pea" can't be traced, and no "a" is next to the "r", so neither can "rain".

Example 2:

Input: board = [
  ["a", "b"],
  ["c", "d"]
], words = ["abdb", "ad"]
Output: []
Explanation: "abdb" would go a → b → d and then back to "b", but that cell is already used in this word.
"a" and "d" touch only at a corner, so "ad" can't be traced either.

Example 3:

Input: board = [
  ["s", "e", "e"],
  ["n", "e", "t"]
], words = ["see", "seen", "set", "net", "tee", "teen"]
Output: ["net", "see", "seen", "tee"]
Explanation: "see" can be traced in two ways (its last "e" is either to the right or below), but it is listed once.
"seen" goes s → e → e (the one below) → n, so the path of "see" is the start of the path of "seen".
"set" can't be traced: the only "e" next to "s" is not next to "t". Neither can "teen": in every path t → e → e, the second "e" is the top middle one, which is not next to "n".

 

Constraints:

  • 1 <= R, C <= 12
  • Every cell of board holds a lowercase English letter.
  • 1 <= words.length <= 3 * 104
  • 1 <= words[i].length <= 10
  • words[i] consists of lowercase English letters, and all the words are different.

Note:

Searching the board once for every word repeats the same work for words that start the same way. Put the words in a trie instead, and search the board once: a depth-first search from each cell follows only the trie's paths. With words of at most L letters, each search goes at most L cells deep, so the time is O(R * C * 4L), plus the time to build the trie, whatever the number of words.

STEP 1 OF 26
    Ctrl + Enter to check

    RUST · TRIES

    Word Search Ii in Rust, explained

    Problem overview

    find_words receives a grid of letters, board, as a Vec<Vec<char>>, and a vector of words. It returns every word that can be traced on the board. A word is traced along a path of cells: each next letter sits in a cell directly above, below, left or right of the previous one, and no cell is used twice within one word. Each word is returned once, in any order. The examples list them alphabetically, so the order in which your function finds them doesn't matter.

    On the board oaan / etae / ihkr / iflv with the words oath, pea, eat and rain, the answer is ["eat", "oath"]. On ab / cd, the word abdb would need the cell of b twice, and ad would need a diagonal step, so nothing is found. On see / net, the word see can be traced in two ways, but it is returned once.

    Approach: search the board once, guided by a trie

    The direct method runs a depth-first search from every cell for every word. Words that start the same way, such as see and seen, repeat the same work, and with up to 30,000 words that adds up.

    A trie fixes that. It stores all the words in one tree where each level is one more letter, so a shared beginning is stored and followed once. Then one depth-first search from each cell looks for all the words at the same time: at each step it only moves to a neighbour whose letter continues some word. If no word continues with that letter, the whole branch is cut off.

    The trie node keeps the finished word itself, as a String, instead of a yes/no flag. When the search reaches that node, it already has the word to report. Clearing the string right after reporting means a word reachable along several paths is reported once.

    The search is backtracking. Before stepping to the neighbours, the current cell is overwritten with '#', a character no word contains, so the path can't use it again. When the search leaves the cell, the letter is written back, and the cell is free for other paths.

    With words of at most L letters, a path goes at most L cells deep and has at most four directions at each step, giving O(R · C · 4^L) time for the search, plus the cost of building the trie. The number of words doesn't appear in the search cost.

    Step by step

    1. Give TrieNode a children field, a HashMap<char, TrieNode>, from each next letter to its child. A struct can contain a map of its own type, because the map keeps its values on the heap.
    2. Add a word field, a String. On a node where a word ends, it holds that word. An empty string means no word ends here, which is safe because every word has at least one letter.
    3. TrieNode::new returns a node with an empty map and an empty string.
    4. In find_words, create the trie root. It stands for the empty prefix.
    5. Insert every word with a loop over &words.
    6. Start each word at the root with let mut node = &mut root;, a mutable reference.
    7. Loop over word.chars(). Each letter goes one level down.
    8. Create the missing child. If node.children has no key c, insert a new TrieNode under it.
    9. Move down with get_mut(&c).unwrap(). The child exists by now, so unwrap is safe.
    10. After the letters, store the word in node.word as a clone.
    11. Create found, an empty Vec<String> that every search adds to.
    12. Loop over every row with 0..board.len(), and every column with 0..board[0].len().
    13. Call Self::dfs from each cell with the board, the cell as i32 values, the trie root and found. The coordinates are i32 so that stepping above the first row gives -1 instead of breaking a usize.
    14. Return found with no semicolon.
    15. In dfs, leave when the cell is off the board. The four calls below step to neighbours without checking them, so this check catches them.
    16. Read the cell's letter into letter. It is needed again at the end, to restore the cell.
    17. Leave when node.children has no key letter. No word continues this way. The marker '#' also stops here, which is how a used cell is skipped.
    18. Move down the trie to child, a mutable reference found with get_mut.
    19. If child.word isn't empty, the path spells a word. Push a clone of it onto found and clear it, so the word isn't reported again.
    20. Mark the cell by setting it to '#'.
    21. Search all four neighbours, continuing from child: below, above, right, left.
    22. Restore the letter. Undoing the mark on the way out is what makes this backtracking.

    The solution in Rust

    use std::collections::HashMap;

struct TrieNode {
    children: HashMap<char, TrieNode>,
    word: String,
}

impl TrieNode {
    fn new() -> TrieNode {
        TrieNode { children: HashMap::new(), word: String::new() }
    }
}

impl Solution {
    fn find_words(mut board: Vec<Vec<char>>, words: Vec<String>) -> Vec<String> {
        let mut root = TrieNode::new();
        for word in &words {
            let mut node = &mut root;
            for c in word.chars() {
                if !node.children.contains_key(&c) {
                    node.children.insert(c, TrieNode::new());
                }
                node = node.children.get_mut(&c).unwrap();
            }
            node.word = word.clone();
        }
        let mut found: Vec<String> = Vec::new();
        for row in 0..board.len() {
            for col in 0..board[0].len() {
                Self::dfs(&mut board, row as i32, col as i32, &mut root, &mut found);
            }
        }
        found
    }

    fn dfs(board: &mut Vec<Vec<char>>, row: i32, col: i32, node: &mut TrieNode, found: &mut Vec<String>) {
        if row < 0 || row >= board.len() as i32 || col < 0 || col >= board[0].len() as i32 {
            return;
        }
        let letter = board[row as usize][col as usize];
        if !node.children.contains_key(&letter) {
            return;
        }
        let child = node.children.get_mut(&letter).unwrap();
        if !child.word.is_empty() {
            found.push(child.word.clone());
            child.word.clear();
        }
        board[row as usize][col as usize] = '#';
        Self::dfs(board, row + 1, col, child, found);
        Self::dfs(board, row - 1, col, child, found);
        Self::dfs(board, row, col + 1, child, found);
        Self::dfs(board, row, col - 1, child, found);
        board[row as usize][col as usize] = letter;
    }
}

    Rust details worth a closer look:

    • A mutable cursor into the trie. let mut node = &mut root; is a mutable reference, and the loop reassigns it to point one level lower. The variable is mut because it changes which node it refers to, not because the node is replaced.
    • Insert, then get_mut. Checking contains_key, inserting, and then calling get_mut(&c).unwrap() gives a mutable reference to the child without any ownership trouble. Both calls take &c, a reference to the key.
    • Passing mutable references on. In dfs, board, child and found are already &mut, so the recursive calls pass them as they are. Rust reborrows them for each call, which lets the four calls follow one another.
    • usize and i32. row and col are i32, so row - 1 can be -1. The check at the top rejects negative or too-large values before row as usize is used to index, where a negative value would otherwise turn into a huge number.
    • char and String. The board holds char values, which are single Unicode characters, so '#' is written with single quotes. child.word.clear() empties the string in place, and is_empty() tests for it.
    • Cloning the word. child.word.clone() copies the string into found, because the trie still owns the original until it is cleared.
    • The use line. HashMap needs use std::collections::HashMap; at the top.

    Complexity

    Time: O(R · C · 4^L) for the search, where L is the longest word, plus O(W · L) to build the trie for W words. A search starts from each of the R · C cells, goes at most L cells deep, and has at most four directions per step. In practice the trie cuts most branches early, and a used cell can't be revisited. The search doesn't depend on how many words there are.

    Space: O(W · L) for the trie, since every letter of every word can take a node, plus O(L) for the recursion and the answer's size. The board is changed in place and restored.

    Edge cases and common mistakes

    • Reusing a cell. On ab / cd, abdb fails because the second b is the cell already marked '#'. Without the marker, the search would walk a, b, d, b and report it.
    • Diagonals. Only four directions are tried, so ad on ab / cd isn't found.
    • Duplicates. On see / net, see has two paths. With the clear() line removed, the result on that board, sorted, is ["net", "see", "see", "seen", "tee", "tee"]; with it, each word appears once.
    • Forgetting to restore the letter. Leaving a '#' on the board would hide cells from later searches and from the other starting cells.
    • A word that is a prefix of another. see and seen both come out: the node for see reports its word and the search continues below it.
    • One-cell boards. A board a with the word a finds it; with the word aaa it doesn't, since the one cell can't be used again.
    • The order of the result. The function returns words in the order they are found, such as ["oath", "eat"] for the first example, not alphabetically. Sort the result if you need alphabetical order.

    Testing

    Running the reference solution and sorting the result gives:

    • board oaan / etae / ihkr / iflv, words oath, pea, eat, rain gives ["eat", "oath"].
    • board ab / cd, words abdb, ad gives [].
    • board see / net, words see, seen, set, net, tee, teen gives ["net", "see", "seen", "tee"].
    • board a, words a gives ["a"].
    • board a / a (two rows), words aaa gives [].
    • board ab (one row), words ab, ba, a, b gives ["a", "ab", "b", "ba"].
    Keep going with Rust500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free