Start learning free

LESSON 352 OF 540 · BACKTRACKING

Word Search in TypeScript: Backtracking with Depth-First Search

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

    TYPESCRIPT · BACKTRACKING

    Word Search in TypeScript, 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. To trace it, start at any cell and move one step at a time to a cell directly above, below, left or right, never diagonally. The cells visited must spell the word in order, and no cell may be used twice. Letters are case-sensitive.

    Take the 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 "ABCB" the first three letters follow 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

    The word can start anywhere, so the search tries every cell as the first letter. From a cell that matches, it moves to each of the four neighbours and asks the same question for the next letter. That is a depth-first search: follow one path as deep as it goes, and when it fails, step back and try another.

    The path must not reuse a cell, so the search needs to remember which cells are on the current path. Instead of a separate table, this solution overwrites the cell with '#', which is never a letter and so never matches any letter of the word. When the search comes back from that cell, it restores the letter. This undoing is the "back" in backtracking: a path tried later is free to use the cell again.

    A path stops at its first wrong letter, so most branches die after a step or two. The worst case is still large, because every cell can start a search that branches up to four ways for each letter of the word.

    Step by step

    exist: try every start

    1. Loop over rows with row from 0 while row < board.length.
    2. Loop over columns inside it, with col up to board[0].length.
    3. Call this.dfs with the board, the word, the cell and index 0, the first letter. If it returns true, return true at once: one start that works is enough.
    4. Return false after both loops: no cell could start the word.

    dfs: match one letter and ask the neighbours

    The helper dfs(board, word, row, col, index) answers whether the letters of word from index on can be traced starting at cell (row, col).

    1. All letters matched. If index === word.length, return true. This test comes first on purpose: the cell before this one matched the last letter, so the current cell may even lie outside the board.
    2. Outside the board. Return false if row or col is below 0 or past the last row or column. Four conditions are joined with ||. Checking here spares every caller from checking its neighbours.
    3. Wrong letter. Return false if board[row][col] !== word[index]. A cell already on the path holds '#', so it fails here too.
    4. Mark the cell by setting it to '#'.
    5. Prepare the answer. Create found with let, set to false. The cell has to be unmarked before returning, so the function can't return the moment a neighbour succeeds.
    6. Write the moves as data: directions holds the pairs [-1, 0], [1, 0], [0, -1], [0, 1]: up, down, left, right as changes in row and column.
    7. Try each neighbour. A for...of loop unpacks each pair into [dr, dc], and found = found || this.dfs(..., row + dr, col + dc, index + 1). The next letter is the next index.
    8. Unmark the cell by putting word[index] back. This is the letter the cell held, because it matched.
    9. Return found.

    The solution in TypeScript

    class Solution {
    exist(board: string[][], word: string): boolean {
        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: string[][], word: string, row: number, col: number, index: number): 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] = '#';
        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;
    }
}

    Details worth knowing:

    • The board is shared. board is an array of arrays, which JavaScript passes by reference, so every call works on the same one, so writing '#' in one call is visible in all the deeper calls. That is what makes the marking work, and it is why the letter must be restored. After exist returns, the board holds its original letters again.
    • Destructuring. const [dr, dc] of directions takes each two-number array apart. Since directions is an array of arrays of numbers, dr and dc are numbers.
    • Short-circuit ||. The right side of found || this.dfs(...) runs only while found is still false. Once one neighbour completes the word, the remaining neighbours are skipped. Because found is assigned and returned only after the unmarking, the board is restored either way.
    • Order of the tests. The bounds test must come before board[row][col]. Reading board[-1] gives undefined, and then board[-1][0] throws a TypeError.
    • Types are erased. string[][] and boolean are checked by the compiler and disappear in the generated JavaScript.

    Complexity

    Time: O(R · C · 4^L) in the worst case, where R and C are the numbers of rows and columns and L is the length of the word. Each of the R·C cells can start a search. Each call has up to four neighbours (three after the first, since the cell it came from is marked), and the path is at most L letters deep. In practice it is much faster, because a path ends at its first wrong letter.

    Space: O(L) for the recursion, one call per letter matched so far. The board itself is reused, with no visited table.

    Edge cases and common mistakes

    • Forgetting to unmark. If the letter isn't restored, a cell stays '#' after one failed path, and later paths that need it fail. The board would also be left damaged for the caller.
    • Reusing a cell. Without the marking, [["a","a"]] with the word "aaa" would wrongly succeed by going back and forth. With it the answer is false.
    • Checking the word's end too late. If the index === word.length test came after the bounds test, a word ending at an edge cell would fail, because its last neighbour falls outside the board.
    • Case. [["a"]] with "A" gives false: the letters differ.
    • Single cell. A one-cell board works for a one-letter word, and any longer word fails.
    • Diagonal moves. Only the four directions in directions are allowed. Adding diagonal pairs would accept paths the problem forbids.

    Testing

    On the board [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]]:

    • "ABCCED" gives true.
    • "SEE" gives true.
    • "ABCB" gives false.
    • "ABCCEDA" gives true: the path continues from D (2,1) left to the A at (2,0).
    • "a" gives false, because the board holds only capital letters.

    On small boards: [["a"]] with "a" gives true, with "aa" gives false, and [["a","a"]] with "aaa" gives false.

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