Start learning free

LESSON 352 OF 540 · BACKTRACKING

Word Search in Scala: 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 15
    Ctrl + Enter to check

    SCALA · BACKTRACKING

    Word Search in Scala, explained

    Problem overview

    The method exist gets board, an Array[Array[Char]] grid of letters, and a word. It returns true when 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 of the current one, never diagonally. The cells visited must spell the word in order, and no cell may be used twice. Letters are case-sensitive.

    Take this board:

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

    "ABCCED" is found: A at row 0, column 0, then B, then C at (0,2), the C below it at (1,2), the E below that at (2,2) and finally the D to its left. "SEE" is found by S at (1,3), E at (2,3), E at (2,2). "ABCB" is not found: after A, B, C the only B next to the C is the one already used.

    Approach: depth-first search with undo

    A word can begin in any cell, so the method tries every cell as the first letter. From a start, it needs to explore paths, and a path can branch four ways at each step. This is backtracking: extend the path one letter at a time, and when a branch fails, undo the last step and try the next option.

    One recursive call does one job: dfs(board, word, row, col, index) answers whether the letters of word from position index to the end can be traced starting at cell (row, col). It stops at the first wrong letter, so most paths die after a step or two.

    The rule that a cell can't be reused needs a record of the current path. Instead of a separate table, the search overwrites the cell with '#' while it is on the path. The board holds only letters, so '#' never matches a letter of the word, and a deeper call that steps on this cell fails the letter test by itself. When the call finishes, it writes the original letter back, so later paths can use the cell again.

    In the worst case, the search from each of the R·C cells branches four ways for the first letter and at most three ways for each later letter, because one neighbour is the cell it came from. With a word of length L this is O(R·C·4^L) time. The recursion is at most L calls deep, so the extra space is O(L).

    Step by step

    exist

    1. Loop over the rows with for (row <- board.indices). indices is the range of valid positions, from 0 to the last.
    2. Loop over the columns with board(0).indices. Together the two loops visit every cell as a possible start.
    3. Call dfs with the start cell and index 0, the first letter. If it returns true, return true at once: one successful start is enough.
    4. Return false after both loops. No start worked.

    dfs

    1. Declare the helper with the board, the word, the cell and the index of the letter this cell must hold, returning Boolean.
    2. All letters matched: if index == word.length, return true. This test comes first on purpose. The previous call matched the last letter, so the current cell is irrelevant, and it may even lie outside the board.
    3. Outside the board: return false if the row or column is below 0 or past the last one. Edge cells have neighbours outside the grid, and checking here saves every caller from doing it.
    4. Wrong letter: return false if board(row)(col) differs from word(index). A cell on the current path holds '#', so it fails here too.
    5. Mark the cell by setting it to '#'.
    6. Prepare the result: a var found starting at false. The method can't return as soon as a neighbour succeeds, because the cell must be restored first.
    7. Write the four moves as data: directions is an array of (row change, column change) pairs for up, down, left and right.
    8. Loop over the moves and update found with found || dfs(...) for the neighbour at row + d(0), col + d(1), looking for the letter at index + 1. The || skips the call once found is already true.
    9. Unmark the cell by putting word(index) back. This is the backtracking step.
    10. Return found.

    The solution in Scala

    class Solution {
    def exist(board: Array[Array[Char]], word: String): Boolean = {
        for (row <- board.indices) {
            for (col <- board(0).indices) {
                if (dfs(board, word, row, col, 0)) {
                    return true
                }
            }
        }
        return false
    }

    def dfs(board: Array[Array[Char]], word: String, row: Int, col: Int, index: Int): Boolean = {
        if (index == word.length) {
            return true
        }
        if (row < 0 || row >= board.length || col < 0 || col >= board(0).length) {
            return false
        }
        if (board(row)(col) != word(index)) {
            return false
        }
        board(row)(col) = '#'
        var found = false
        val directions = Array(Array(-1, 0), Array(1, 0), Array(0, -1), Array(0, 1))
        for (d <- directions) {
            found = found || dfs(board, word, row + d(0), col + d(1), index + 1)
        }
        board(row)(col) = word(index)
        return found
    }
}

    The Scala details worth noticing:

    • Arrays are mutable and indexed with parentheses. board(row)(col) reads a cell, and board(row)(col) = '#' writes it. The board is shared by every recursive call, so the mark is visible to all of them. That is the point, and it is also why the undo matters: without it the board would stay damaged for the next start.
    • Char comparisons. word(index) is a Char, and '#' is a Char literal. Comparing two Char values with != compares the characters, and uppercase and lowercase letters differ.
    • for (d <- directions) walks an array whose elements are themselves arrays of two Int, so d(0) and d(1) are the row and column changes.
    • return inside a for loop. The loop body is a function under the hood. Scala 3.5 still accepts return there and the code works, but the compiler prints a warning that non-local returns are no longer supported. The message points to boundary and boundary.break in scala.util as the replacement.
    • Short-circuit ||. The right side is evaluated only when the left side is false, so after one neighbour finishes the word, the remaining neighbours aren't searched.

    Complexity

    Time: O(R·C·4^L) in the worst case, with R rows, C columns and a word of L letters. Each of the R·C cells starts a search, and a search goes at most L letters deep with at most four choices at each. The worst case needs a board and a word that keep matching for many letters, such as a grid of a single repeated letter and a word that ends with a different one. Ordinary boards stop much earlier.

    Space: O(L). The marks live inside the board, so the only extra memory is the call stack, with one call per letter matched so far.

    Edge cases and common mistakes

    • Reusing a cell. On a one-row board a a, the word "aaa" is not found: it needs three cells and the board has two. Without the '#' mark, the search would step back and forth between the same two cells and answer true.
    • Forgetting to unmark. The cell stays '#' after a failed branch, and later paths that need that letter fail. A correct run leaves the board exactly as it was, whether exist returns true or false.
    • Checking the index after the bounds. If the index == word.length test came after the bounds test, a word ending at a corner would fail, because the neighbour after its last letter is outside the board.
    • Case sensitivity. On a board holding a and b, the word "A" returns false.
    • Single cell. A 1x1 board with a finds "a" and not "aa".
    • Diagonal moves. Only the four directions are in the array, so the search never steps diagonally.
    • Returning when a neighbour succeeds. Returning inside the loop would skip the restore step. Collecting the answer in found and returning at the end keeps the board intact.

    Testing

    On the board above:

    • "ABCCED" gives true.
    • "SEE" gives true.
    • "ABCB" gives false.
    • "ABCESEEEFS" gives false.
    • "ASAD" gives true: A (0,0), S (1,0), A (2,0), D (2,1).
    • "a" gives false, because the board has only uppercase letters.

    On other boards: a alone with "a" gives true and with "aa" gives false; a a with "aaa" gives false; a b with "ba" gives true.

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