Start learning free

LESSON 348 OF 536 · BACKTRACKING

Word Search in Python: Backtracking

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 a list of rows, and each row is a list 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

    PYTHON · BACKTRACKING

    Word Search in Python, explained

    Problem overview

    The function exist(board, word) receives a grid of letters, a list of rows where each row is a list of one-letter strings, and a string word. It returns True when the word can be traced through the grid and False otherwise.

    Tracing means starting at any cell and moving up, down, left or right, one cell per letter, so that the cells spell the word in order. Diagonal moves are not allowed, each cell can be used at most once, and letters are case-sensitive.

    Take this grid:

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

    The word "ABCCED" is found: A at row 0, column 0, then B, C along the top row, down to the C in row 1, down to the E in row 2, and left to D. "SEE" is also found, going from the S at the end of row 1 down to the E below it and left to the next E. "ABCB" is not: the path A, B, C reaches the C in row 0, but the only B next to it is the one already used.

    Approach: depth-first search with backtracking

    The word can start anywhere, so the function tries every cell as the first letter. From a starting cell, the search is a depth-first search: match one letter, then ask the four neighbours to match the rest of the word. Whenever a cell holds the wrong letter, that path stops at once, which keeps the search small in practice.

    The rule that each cell is used once needs bookkeeping. While a cell is part of the current path, no deeper call may step on it again. The code marks the cell by overwriting its letter with '#', which is never a letter, so the normal "does this cell hold the right letter?" test also rejects cells already on the path. When the search comes back out of the cell, it restores the letter. That undo is the "back" in backtracking: a different path, tried later, may use this cell again.

    In the worst case each cell starts a search that branches into up to 4 directions for each letter of the word (3 after the first, since the cell it came from is marked). The time is O(R * C * 4^L), where R and C are the grid's dimensions and L is the length of the word. In practice most branches stop at the first wrong letter.

    Step by step

    The outer function

    1. Loop over the rows, with row in range(len(board)).
    2. Loop over the columns inside it, with col in range(len(board[0])). Every row has the same length, so the first row tells the width.
    3. Try the cell as the start. Call self.dfs(board, word, row, col, 0), where 0 is the index of the first letter. If it returns True, return True straight away: one working start is enough.
    4. Return False after both loops. Reaching that line means no cell could start the word.

    The helper dfs

    1. Declare it with the board, the word, a cell and index, the position in word of the letter this cell must hold. It answers whether the letters from index to the end can be traced starting here.
    2. If index equals len(word), return True. The previous cell matched the last letter, so the word is complete. This test comes first because the current cell may be off the board, and then the later tests would be wrong to reject it.
    3. Return False if the cell is outside the board. Neighbours of edge cells land outside, and checking here spares every caller from doing it.
    4. Return False if the cell's letter is not word[index]. This also rejects cells marked '#'.
    5. Mark the cell by setting it to '#'.
    6. Start with found = False. The function can't return as soon as a neighbour succeeds, because the cell must be unmarked first.
    7. List the four moves as [row change, column change] pairs. One loop over this data replaces four copies of the same call.
    8. Loop over the pairs, unpacking each into dr and dc.
    9. Update found with found or self.dfs(...) on the neighbour, with index + 1 for the next letter. Because or evaluates its right side only while found is still False, the remaining directions are skipped after the first success.
    10. Restore the cell: put word[index] back into board[row][col].
    11. Return found.

    The solution in Python

    class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        for row in range(len(board)):
            for col in range(len(board[0])):
                if self.dfs(board, word, row, col, 0):
                    return True
        return False

    def dfs(self, board, word, row, col, index):
        if index == len(word):
            return True
        if row < 0 or row >= len(board) or col < 0 or col >= len(board[0]):
            return False
        if board[row][col] != word[index]:
            return False
        board[row][col] = '#'
        found = False
        directions = [[-1, 0], [1, 0], [0, -1], [0, 1]]
        for dr, dc in directions:
            found = found or self.dfs(board, word, row + dr, col + dc, index + 1)
        board[row][col] = word[index]
        return found

    Some Python details are worth noting.

    • The board is changed in place. Lists are mutable and passed by reference, so every call of dfs sees the same grid. That is what makes the '#' mark visible to deeper calls. Because every mark is undone before dfs returns, the board is the same after exist finishes as before it started.
    • Negative indexes wrap around in Python. board[-1] is the last row, not an error. That is why the bounds test must come before any read of board[row][col]: without it, a move off the top or left edge would silently read the opposite edge.
    • for dr, dc in directions unpacks each two-element list into two names.
    • found or self.dfs(...) returns the first truthy operand, and both operands here are booleans, so found stays a proper True or False.

    Complexity

    The time is O(R * C * 4^L) in the worst case, from the branching described above, with L at most 15 and a grid of at most 6 by 6 here. The extra space is O(L): the recursion goes at most one call per letter of the word, and the marks are made inside the existing grid, so no visited set is needed.

    Edge cases and common mistakes

    • Forgetting to unmark. If the cell keeps its '#' after a failed branch, later paths can no longer pass through it, and the function can miss words that exist.
    • Checking the end of the word too late. If the "word complete" test comes after the bounds test, a word whose last letter sits on an edge cell would be rejected, because its final neighbour call lands off the board.
    • Reusing a cell. The word "ABCB" on the grid above is False for exactly this reason. Without the marks it would be True.
    • Case. "abc" is not found on a grid of capital letters.
    • A one-letter word needs only one matching cell. A single-cell grid holding "a" answers True for "a" and False for "aa", since the one cell can't be used twice.
    • Diagonals. Only the four directions in the list are allowed.

    Testing

    On the grid above, the results are:

    wordresult
    "ABCCED"True
    "SEE"True
    "ABCB"False
    "A"True
    "ABCESEEDAS"True
    "abc"False

    Also try [["a"]] with "a" (True) and with "aa" (False), and [["a", "a"]] with "aaa" (False: two cells can't spell three letters).

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