Start learning free

LESSON 348 OF 536 · BACKTRACKING

Word Search in Java: Backtracking DFS 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

    JAVA · BACKTRACKING

    Word Search in Java, explained

    Problem overview

    The method exist receives a grid of letters, char[][] board, and a String word. It returns true if the word can be traced through the grid and false otherwise. A trace starts at any cell and moves one step at a time up, down, left or right, never diagonally. The visited cells must spell the word in order, a cell can be used at most once, and the letters are case-sensitive.

    Take this board:

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

    For "ABCCED" the path is A (0,0), B (0,1), C (0,2), C (1,2), E (2,2), D (2,1), so the answer is true. For "SEE" it is S (1,3), E (2,3), E (2,2), also true. For "ABCB" the path A, B, C works along the top row, but the only B next to that C is the one already used, so the answer is false.

    Approach: depth-first search with backtracking

    Nothing in the grid says where the word starts, so every cell is a candidate first letter. From a cell that matches, the next letter must sit in one of its four neighbours, and from there the next one, and so on. That is a depth-first search: follow one path as far as it goes, and when it fails, return to the last choice and try another.

    The rule "each cell at most once" needs memory of the current path. Instead of a separate visited array, the search overwrites the cell with '#' while it is on the path. Since the board holds only letters, a cell marked '#' can never equal a letter of the word, so a deeper call that steps on it fails its letter test automatically.

    The marking must be undone. Once a path through a cell has failed, a different path found later may legitimately use that cell, so the search puts the letter back before returning. That undo is what makes it backtracking: the board is the same after the call as before it. In the lesson's runs, the board passed to exist compared equal to a fresh copy afterwards, for both true and false answers.

    The search stays small in practice because a path ends at its first wrong letter. In the worst case, the search from each of the R·C cells branches four ways for each of the L letters of the word (three ways after the first, since the previous cell is marked), which gives O(R·C·4^L) time.

    Step by step

    The outer method

    1. Loop over every row and column. Two nested for loops, with row up to board.length and col up to board[0].length, visit each cell as a possible start.
    2. Call dfs(board, word, row, col, 0). The last argument is the index of the first letter. It returns true when the word can be traced from that cell.
    3. Return true at the first success. One start that works is enough.
    4. Return false after both loops, because no cell could start the word.

    The helper dfs

    1. Declare it with the board, the word, a cell and an index: the position in word of the letter this cell must hold. It asks whether the letters from index to the end can be traced starting at this cell.
    2. If index == word.length(), return true. Every letter has been matched. This test comes first because the cell that made the last match is behind us, and the current cell may even be outside the board.
    3. Return false for a cell outside the board. Neighbours of edge cells fall outside, and checking here saves each caller from doing it.
    4. Return false if the cell's letter differs from word.charAt(index). This also rejects cells already on the path, which hold '#'.
    5. Mark the cell by setting it to '#'.
    6. Create found, set to false. The method can't return as soon as a neighbour succeeds, because the cell must be unmarked first.
    7. Write the four moves as data: an int[][] of row and column changes for up, down, left and right.
    8. Loop over the moves and set found = found || dfs(...) for the neighbour, with index + 1 for the next letter.
    9. Unmark the cell by writing word.charAt(index) back. That was the cell's letter, because it matched.
    10. Return found.

    The solution in Java

    class Solution {
    public boolean exist(char[][] board, String word) {
        for (int row = 0; row < board.length; row++) {
            for (int col = 0; col < board[0].length; col++) {
                if (dfs(board, word, row, col, 0)) {
                    return true;
                }
            }
        }
        return false;
    }

    boolean dfs(char[][] board, String word, int row, int col, int index) {
        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.charAt(index)) {
            return false;
        }
        board[row][col] = '#';
        boolean found = false;
        int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        for (int[] d : directions) {
            found = found || dfs(board, word, row + d[0], col + d[1], index + 1);
        }
        board[row][col] = word.charAt(index);
        return found;
    }
}

    Java details worth noticing:

    • A grid is an array of arrays. board.length is the number of rows and board[0].length the number of columns. This is safe here because the lesson guarantees at least one row and equal row lengths.
    • Arrays are passed by reference. dfs changes the very board that exist received, so the marks are visible to every deeper call. The same fact is why the unmark step matters: nothing else restores the board.
    • char compares with !=. board[row][col] != word.charAt(index) compares two primitive char values, so no equals is needed. Uppercase and lowercase letters are different values, which gives the case-sensitive behaviour.
    • Short-circuit ||. In found || dfs(...), the call on the right runs only while found is false. Once one neighbour finishes the word, the others are skipped, but the unmark line after the loop still runs.
    • Array initializer. int[][] directions = {{-1, 0}, ...} is allowed at the declaration. Each element is itself an int[], which the for-each loop reads as d.

    Complexity

    Time: O(R·C·4^L), where R and C are the numbers of rows and columns and L is the length of word. There are R·C starting cells, and each search goes at most L letters deep with at most four neighbours tried per level. In practice a path stops at its first wrong letter, so it is usually much faster.

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

    Edge cases and common mistakes

    • Forgetting to unmark. Without the restoring line, a failed path leaves '#' cells behind and later paths miss valid routes. The tracing of "ASADFBCCEESE", which uses every cell, returns true only because cells are released properly.
    • Reusing a cell. "ABCB" returns false: the second B is the one already used. A one-cell board {{'a'}} with the word "aa" returns false for the same reason, and the row {{'a', 'a'}} with "aaa" returns false.
    • Checking the end of the word too late. If the index == word.length() test came after the bounds test, a word that ends at a corner would fail, because the next neighbour is off the board.
    • Testing bounds after reading the cell. Reading board[row][col] before the range checks throws ArrayIndexOutOfBoundsException at the edges.
    • Case. "a" against the sample board returns false, while "A" returns true.
    • Diagonal moves. Only four directions are allowed. "ABFSA" is true using side-by-side steps only: A (0,0), B (0,1), F (1,1), S (1,0), A (2,0).
    • Returning early inside the loop. Writing if (dfs(...)) return true; inside the direction loop would skip the unmark step and leave '#' marks in the board.

    Testing

    On the sample board, these words give:

    • "ABCCED" gives true.
    • "SEE" gives true.
    • "ABCB" gives false.
    • "ASADFBCCEESE" gives true: a path that uses every one of the 12 cells.
    • "ABCESEEEFS" gives false.
    • "ABFSA" gives true.

    On small boards, {{'a'}} with "a" gives true, and with "aa" gives false.

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