Start learning free

LESSON 348 OF 536 · BACKTRACKING

Word Search in JavaScript: Backtracking with DFS

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

    JAVASCRIPT · BACKTRACKING

    Word Search in JavaScript, explained

    Problem overview

    The method exist(board, word) receives a grid of letters, an array of rows where each row is an array of one-letter strings, 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 to a side-by-side neighbour (up, down, left or right) for each following letter. A cell can be used at most once in one trace, and letters are case-sensitive.

    With the board [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], the word "ABCCED" is found: A at (0,0), B at (0,1), C at (0,2), C at (1,2), E at (2,2), D at (2,1). The word "SEE" is found too. The word "ABCB" is not: the only B next to the C in the top row is the one the path already used.

    Approach: try every start, then backtrack

    The word can begin in any cell, so the method tries every cell as the first letter. From a starting cell, a recursive helper dfs matches one letter, then asks the four neighbours to match the rest. That is a depth-first search.

    Each cell may be used only once on a path, so the helper needs to remember which cells are on the current path. The lesson does this in place: when a cell matches, it is overwritten with '#', which is never a letter, so any deeper call that reaches that cell fails its comparison. When the search comes back from the neighbours, the cell gets its letter back. That undo is the backtracking step: a different path, tried later, may use the cell again.

    A path stops at its first wrong letter, so in practice most branches die after a few cells. In the worst case the search is O(R·C·4^L), where R and C are the board's dimensions and L is the word's length. The constraints (at most 6 by 6 and 15 letters) keep that manageable.

    Step by step

    exist

    1. Loop over every row with row, and inside it over every column with col, up to board[0].length.
    2. At each cell, call this.dfs(board, word, row, col, 0), asking whether the word can be traced starting here with index 0, the first letter. If so, return true at once, because one working start is enough.
    3. After both loops, return false: no cell could start the word.

    dfs

    1. If index equals word.length, every letter has been matched, so return true. This check comes first because the cell just stepped onto may be outside the board: the previous cell matched the last letter, and this one doesn't matter.
    2. If the cell is outside the board (a negative row or column, or one past the last), return false. Testing it here means callers don't have to check their neighbours.
    3. If the cell's letter isn't word[index], return false. A cell already on the path holds '#', so it fails here too.
    4. Mark the cell by setting it to '#'.
    5. Declare found as false. The method can't return as soon as a neighbour succeeds, because the cell must be restored first.
    6. Write the four moves as [row change, column change] pairs in directions, and loop over them, unpacking each pair into dr and dc.
    7. In the loop, set found to found || the result of dfs on the neighbour with index + 1.
    8. Put word[index] back into the cell, then return found.

    The solution in JavaScript

    class Solution {
    exist(board, word) {
        for (let row = 0; row < board.length; row++) {
            for (let col = 0; col < board[0].length; col++) {
                if (this.dfs(board, word, row, col, 0)) {
                    return true;
                }
            }
        }
        return false;
    }

    dfs(board, word, row, col, 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[index]) {
            return false;
        }
        board[row][col] = '#';
        let found = false;
        const directions = [[-1, 0], [1, 0], [0, -1], [0, 1]];
        for (const [dr, dc] of directions) {
            found = found || this.dfs(board, word, row + dr, col + dc, index + 1);
        }
        board[row][col] = word[index];
        return found;
    }
}

    The JavaScript details worth knowing:

    • Array destructuring in for...of. for (const [dr, dc] of directions) takes each two-number array apart into dr and dc.
    • Short-circuit ||. found || this.dfs(...) evaluates the right side only while found is false. Once one neighbour finishes the word, the remaining directions are skipped, but the loop still reaches the line that restores the cell.
    • The board is changed and restored. The method writes '#' into the array it was given, so the caller's board is briefly modified. Every '#' is replaced before the method returns, which is why the board is the same afterwards: running "ABCB" on the example board and printing it afterwards shows the original three rows.
    • Strings are indexable. word[index] gives the one-character string at that position, and !== compares it with the board's one-character string.
    • this.dfs. The helper is a method, so it is called through this.

    Complexity

    Time: O(R·C·4^L) in the worst case. There are R·C starting cells, and each search goes at most L letters deep with up to 4 choices per level (3 after the first, since the cell it came from is marked). Wrong letters cut most branches early.

    Space: O(L). The recursion is at most L calls deep. The marking is done in the board itself, so no visited array is needed.

    Edge cases and common mistakes

    • Reusing a cell. On a board holding [["a", "a"]], the word "aaa" gives false, because only two cells exist. Without the marking, the search would bounce between them.
    • Forgetting to unmark. If the cell isn't restored, a failed path leaves '#' behind, and later paths can no longer use those cells. On the board [["a","a","b"],["b","b","a"]], the word "abaa" is traceable, but a version without the restore line returns false for it.
    • Testing the index too late. The call that follows the last matched letter has no letter left to match: word[index] is undefined, and it may also be outside the board. If the index === word.length check came after the other two, every search would fail.
    • Returning inside the loop. Returning as soon as a neighbour succeeds skips the restore step and leaves '#' in the board.
    • Case. [["a", "A"]] contains "aA", but searching for "aa" gives false.
    • Single cell. [["a"]] contains "a" but not "aa".

    Testing

    • The example board with "ABCCED" gives true.
    • The example board with "SEE" gives true.
    • The example board with "ABCB" gives false.
    • The example board with "ABFSAD" gives true: A (0,0), B (0,1), F (1,1), S (1,0), A (2,0), D (2,1).
    • [["a"]] with "a" gives true, and with "aa" gives false.
    • [["a", "a"]] with "aaa" gives false.
    Keep going with JavaScript500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free