Start learning free

LESSON 355 OF 543 · BACKTRACKING

Word Search in Rust: Backtracking in O(R·C·4^L)

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

Given a grid of letters board and a string word, return true if word can be traced in the grid, and false otherwise.

The grid is an array of rows, and each row is an array of letters, one letter per cell. Rows are numbered from 0, top to bottom, and columns from 0, left to right.

To trace a word, start at any cell and move, one letter at a time, to a cell side by side with the current one: up, down, left or right, never diagonally. The cells must spell word in order, and each cell can be used at most once. Letters are case-sensitive: a and A are different letters.

 

Example 1:

Input: board = [
  ["A","B","C","E"],
  ["S","F","C","S"],
  ["A","D","E","E"]
], word = "ABCCED"
Output: true
Explanation: Start at the A in row 0, column 0, and go right to B and C,
down to the C in row 1, down to the E in row 2, and left to D:
A (0,0) -> B (0,1) -> C (0,2) -> C (1,2) -> E (2,2) -> D (2,1)

Example 2:

Input: board = [
  ["A","B","C","E"],
  ["S","F","C","S"],
  ["A","D","E","E"]
], word = "SEE"
Output: true
Explanation: S (1,3) -> E (2,3) -> E (2,2)

Example 3:

Input: board = [
  ["A","B","C","E"],
  ["S","F","C","S"],
  ["A","D","E","E"]
], word = "ABCB"
Output: false
Explanation: A -> B -> C works along the top row, but the only B next to that C
is the one the path already used, and a cell can't be used twice.

 

Constraints:

  • board has 1 to 6 rows and 1 to 6 columns, and every row has the same number of cells.
  • 1 <= word.length <= 15
  • board and word contain only lowercase and uppercase English letters.

Note:

The tutorial uses backtracking: a depth-first search from every cell. One call checks one cell against one letter of word. If they match, it marks the cell as used, asks its four neighbours for the next letter, and then unmarks the cell, so that paths tried later can use it again. A path stops at its first wrong letter, which keeps the search small in practice.

In the worst case, the search from each of the R·C cells branches into 4 directions for each of the L letters of word (3 after the first, since the cell it came from is used): O(R·C·4L) time, where R and C are the numbers of rows and columns and L is the length of word. The extra space is O(L), one call per letter matched so far.

STEP 1 OF 16
    Ctrl + Enter to check

    RUST · BACKTRACKING

    Word Search in Rust, explained

    Problem overview

    The function exist receives a grid of letters, board, as a Vec<Vec<char>>, and a word. It returns true if the word can be traced through the grid. A trace starts at any cell and moves one step at a time to a cell directly above, below, left or right, never diagonally. The visited cells must spell the word in order, no cell can be used twice, and letters are case-sensitive.

    Take this board:

    A B C E
S F C S
A D E E

    The word "ABCCED" can be traced as A (0,0), B (0,1), C (0,2), C (1,2), E (2,2), D (2,1), so the answer is true. "SEE" works too: S (1,3), E (2,3), E (2,2). "ABCB" fails. A, B and C are along the top row, but the only B next to that C is the one already used.

    Approach: depth-first search with backtracking

    Since the word can start anywhere, try every cell as the first letter. From a starting cell, the search is a depth-first search: match the current cell against the current letter, then ask each of the four neighbours to match the next letter.

    The rule "each cell at most once" needs memory of the current path. The solution writes it into the board itself: when a cell matches, it is overwritten with '#', which is never a letter, so any deeper step that reaches it fails the letter test. When all four neighbours have been tried, the original letter is put back. That last part is the backtracking: the cell is free again for paths that are tried later and don't go through it here.

    Here is the search for "ABCB" starting at the A in the corner:

    (0,0) matches A
  (-1,0) outside
  (1,0) holds S not B
  (0,-1) outside
  (0,1) matches B
    (-1,1) outside
    (1,1) holds F not C
    (0,0) holds # not C
    (0,2) matches C
      (-1,2) outside
      (1,2) holds C not B
      (0,1) holds # not B
      (0,3) holds E not B

    At the second C, the cell below holds a C, not the B the word needs. The cell to its left, the B the path came from, now holds #, so it can't be used again. The last neighbour holds an E. Every branch has failed, each cell is restored on the way back, and the search moves on to the next starting cell. In the end no start works, and the result is false.

    A path dies at its first wrong letter, so the search stays small in practice. The worst case is still large: every cell can start a search, and each step has up to 4 choices (3 after the first, because one neighbour is the cell just left). For a word of length L on R rows and C columns, that is O(R·C·4^L) time.

    Step by step

    1. Turn the word into characters. A Rust String can't be indexed by position, so word.chars().collect() builds a Vec<char>. The new word hides the parameter for the rest of the function.
    2. Loop over every cell. row goes over 0..board.len() and col over 0..board[0].len().
    3. Start a search from each cell. Self::dfs gets the board with &mut, the word with &, the position as i32 values, and 0 as the index of the first letter. If it returns true, so does exist.
    4. Return false after the loops. No cell could start the word.
    5. Write the helper's signature. dfs answers whether the letters of word from index on can be traced starting at the cell (row, col). The board is a mutable borrow so the helper can write its marks, and the word is a shared borrow.
    6. Succeed when every letter is matched. If index == word.len(), the previous cell matched the last letter, so return true. This test comes first because the current cell may lie outside the board.
    7. Fail outside the board. A negative coordinate, or one at or beyond the board's size, returns false. Doing this in the helper saves each caller from checking its neighbours.
    8. Fail on a wrong letter. If the cell isn't word[index], return false. A cell already on the path holds '#' and fails here too.
    9. Mark the cell with '#'.
    10. Create found as false. The cell must be unmarked before returning, so the result can't be returned the moment one neighbour succeeds.
    11. List the four moves as an array of (row change, column change) tuples: up, down, left and right.
    12. Loop over the moves, unpacking each into (dr, dc).
    13. Try each neighbour with found = found || Self::dfs(...), passing index + 1. The || only evaluates its right side while found is still false, so once one neighbour succeeds, the rest are skipped.
    14. Unmark the cell by writing word[index], the letter it matched, back into the board.
    15. Return found.

    The solution in Rust

    impl Solution {
    fn exist(mut board: Vec<Vec<char>>, word: String) -> bool {
        let word: Vec<char> = word.chars().collect();
        for row in 0..board.len() {
            for col in 0..board[0].len() {
                if Self::dfs(&mut board, &word, row as i32, col as i32, 0) {
                    return true;
                }
            }
        }
        false
    }

    fn dfs(board: &mut Vec<Vec<char>>, word: &Vec<char>, row: i32, col: i32, index: usize) -> bool {
        if index == word.len() {
            return true;
        }
        if row < 0 || row >= board.len() as i32 || col < 0 || col >= board[0].len() as i32 {
            return false;
        }
        if board[row as usize][col as usize] != word[index] {
            return false;
        }
        board[row as usize][col as usize] = '#';
        let mut found = false;
        let directions: [(i32, i32); 4] = [(-1, 0), (1, 0), (0, -1), (0, 1)];
        for (dr, dc) in directions {
            found = found || Self::dfs(board, word, row + dr, col + dc, index + 1);
        }
        board[row as usize][col as usize] = word[index];
        found
    }
}

    Rust details worth knowing:

    • Why i32 for coordinates. The neighbour of row 0 is row -1, which a usize can't hold. The helper takes i32 values, checks the bounds, and only then converts with as usize to index the board. Subtracting 1 from a usize that is 0 would panic in a debug build.
    • mut board in the signature. exist owns its copy of the board, and mut lets it lend that copy out as &mut. The caller's board is not affected, and the helper puts every letter back anyway.
    • &mut board and passing it on. Inside dfs, board is already a &mut Vec<Vec<char>>, so recursive calls pass it as it is. Rust reborrows it for the call, and the borrow ends when the call returns.
    • Short-circuit with ||. The right-hand call isn't run once found is true. The marks are still undone, because the restoring line comes after the loop.
    • The tuple array. The type [(i32, i32); 4] is an array of exactly four pairs. for (dr, dc) in directions takes each pair apart in the loop header.
    • Comparing chars. board[row as usize][col as usize] != word[index] compares two char values, and the comparison is case-sensitive: with this board, "abcced" returns false.

    Complexity

    Time: O(R·C·4^L) in the worst case, for R rows, C columns and a word of length L. There are R·C starting cells, and each search can branch 4 ways at each of up to L letters. Wrong letters and used cells cut most branches long before that.

    Space: O(L) extra. The marks live in the board, and the only other memory is the recursion, one call per matched letter. The vector of characters for the word also takes O(L).

    Edge cases and common mistakes

    • A single cell. A board [["A"]] with the word "A" gives true. With the word "AA" it gives false, because the only A can't be used twice.
    • Reusing a cell. On the board of the example, "ABCB" fails because the only B next to the C has been used. A path may go left or up, though: on a board with the single row AB, the word "BA" works.
    • Forgetting to unmark. Without the restoring line, a failed path leaves # cells behind, and later starting cells find the board damaged. Words that exist are reported as missing.
    • Testing the index too late. The call that follows the last letter has index == word.len(). If the letter comparison ran before the index test, it would read word[word.len()], past the end of the vector, and panic.
    • Using the word's characters as marks. Words contain only letters, so '#' is safe as a mark. If a word could contain it, the mark would need to be something else, or a separate visited grid.
    • Diagonal moves. Only the four side-by-side moves are allowed.

    Testing

    On the board above:

    • "ABCCED" gives true.
    • "SEE" gives true.
    • "ABCB" gives false.
    • "ABCCEDX" gives false.
    • "abcced" gives false.

    On other boards, [["A"]] with "A" gives true, [["A"]] with "AA" gives false, and a single row AB with "BA" gives true.

    Keep going with Rust500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free