Word Search

Q: What is the time complexity of Word Search?

The worst case is O(m·n·3^L) for an m × n board and a word of length L . Each of the m·n cells can start a path, and after the first step each cell has at most three unvisited neighbors to try. The extra space is O(L) for the recursion, plus O(m·n) if you copy the board to mark it.

MediumBacktracking Graphs

+10

You get a grid of letters board, given as a list of strings where board[r][c] is the letter in row r, column c, and a string word.

Return true if you can trace word on the grid: start on any cell, and each time step to the cell directly above, below, left or right of the current one, so that the cells you visit spell word in order. A tracing may not use the same cell twice. Otherwise return false. Letters are case sensitive, so a and A are different.

Function

exist(board: string-array, word: string) → boolean

boardstring-array: the grid, one string of letters per row
wordstring: the word to trace
Returnsboolean: whether word can be traced through side-by-side cells, each used at most once

Constraints

1 ≤ board.length ≤ 6
1 ≤ board[i].length ≤ 6, and every row has the same length.
1 ≤ word.length ≤ 20
board and word contain only English letters, uppercase and lowercase.

Examples

Input: board = ["STAR", "POOL", "ENDS"]word = "STOOLS"
Output: true
Explanation: Start on the S at row 0, column 0, then go right to T, down to O, right to the second O, right to L, and down to the S at row 2, column 3. That is six different cells, each next to the one before it.

Input: board = ["STAR", "POOL", "ENDS"]word = "POP"
Output: false
Explanation: The board has a single P, at row 1, column 0. After P and O you need another P, and the only one is the cell the path started on, which cannot be used twice.

Input: board = ["STAR", "POOL", "ENDS"]word = "SAND"
Output: false
Explanation: Every letter of SAND is on the board, but the path breaks at the first step: the only A is at row 0, column 2, and neither S touches it.

+23 hidden tests on Submit

Follow-up

Instead of yes or no, can you count how many different tracings of word the board holds?

Hints

Open them one at a time. Each one gives away a little more.

0 of 3 opened

Solution

No formula answers this: you have to search the paths through the grid. Backtracking does it with one path at a time. You extend the path by one letter, mark each cell while the path owns it, and unmark it when you back up, so a cell is never reused within a path but stays free for every other path. That search is exponential in the length of the word in the worst case, which is fine on a board of at most 6 × 6. Two cheap checks before it, a letter count and starting from the rarer end of the word, often cut the work from tens of thousands of steps to a few dozen.

Backtracking with a visited grid

Intuition

Picture a decision tree. The first choice is the starting cell, and it must hold word[0]. After that, every node is a path that spells the first i letters, and its children are the neighbors that hold word[i] and are not on the path yet. A path that spells the whole word is a success. A path with no such neighbor is a dead end, and you back up to try the next choice.

A visited grid enforces the one-use rule. Mark a cell when the path steps onto it and unmark it when the path steps back off. The unmark is what makes this backtracking: a cell that a dead end walked over must be free again for the next attempt. On the board AA / AB with word AAA, starting at the top left cell, going down gets stuck at the bottom left (its other neighbor is B), and going right gets stuck at the top right. If those cells stayed marked, the answer, bottom left then top left then top right, could never be found.

This is the standard answer, and it is correct and fast enough here. Its cost is the number of paths it explores. After the first move, each step has at most three new directions, so a word of L letters can mean on the order of m·n·3^L paths. Take a 5 × 5 board full of A and the word of 8 As followed by a B. Every path of As is a valid prefix, and the search walks all of them before it learns that no B exists: about 65,000 cell checks to answer false. Each extra letter roughly doubles that count, which is why the next approach checks a few things before it searches.

Algorithm

Make a visited grid of the board's size, all false.
Define dfs(r, c, i): return false if (r, c) is outside the grid, visited, or its letter is not word[i].
If i is the last index of word, return true.
Mark (r, c) visited, try the four neighbors with i+1, then unmark it and return whether any neighbor succeeded.
Call dfs(r, c, 0) from every cell and return true as soon as one succeeds.

def exist(board, word):
    rows, cols = len(board), len(board[0])
    visited = [[False] * cols for _ in range(rows)]

    def dfs(r, c, i):
        # Can word[i:] be traced starting at cell (r, c)?
        if r < 0 or r >= rows or c < 0 or c >= cols:
            return False
        if visited[r][c] or board[r][c] != word[i]:
            return False
        if i == len(word) - 1:
            return True
        visited[r][c] = True   # mark: the current path owns this cell
        found = (dfs(r + 1, c, i + 1) or dfs(r - 1, c, i + 1)
                 or dfs(r, c + 1, i + 1) or dfs(r, c - 1, i + 1))
        visited[r][c] = False  # restore: other paths may use it
        return found

    for r in range(rows):
        for c in range(cols):
            if dfs(r, c, 0):
                return True
    return False

Backtracking with in-place marks and pruning

Intuition

Keep the same search and make two changes. First, mark cells on a private copy of the board instead of in a separate grid: overwrite a cell with # while the path owns it and write the letter back when you back up. # never equals a letter of the word, so the letter check also rejects cells on the path, and the restore is the same undo step as before.

Second, prune before you search. Count the letters. If the word needs more copies of some letter than the board holds, the answer is false without any search. That answers the all-A board with 8 As and a B with no search at all, instead of about 65,000 checks. Start from the rarer end. A path read backwards spells the reversed word on the same cells, so you may search for the reversed word instead. If the last letter is rarer on the board than the first, reverse the word. Fewer cells can start a search, and the rare letter rules out wrong starts on the first step instead of the last.

The second rule matters when the rare letter exists but is out of reach. Put the only B in a corner whose two neighbors are C, and search for 8 As and then a B. The letter count passes. Forwards, the search still walks every A path, about 35,000 cell checks. Reversed, the word starts with B, only one cell can start, its neighbors are not A, and the search ends after about 30 checks.

The worst case is still O(m·n·3^L): a board and word can be built where the letters are balanced and the dead ends come late. The pruning does not change the answer or the bound. It removes the common ways the plain search wastes time, at the cost of one pass to count letters, and the gap grows quickly with the length of the word.

Algorithm

Count each letter on the board and in the word. If the word needs more of any letter than the board has, return false.
If the board holds more copies of word[0] than of the last letter, reverse word.
Copy the board into a grid of characters you can change.
Define dfs(r, c, i): fail if the cell is not word[i]; succeed if i is the last index; otherwise set the cell to #, try each in-bounds neighbor with i+1, put the letter back, and return whether any succeeded.
Run dfs(r, c, 0) from every cell and return true as soon as one succeeds.

from collections import Counter


def exist(board, word):
    rows, cols = len(board), len(board[0])

    # Pruning 1: the board must hold every letter as many times as the word uses it.
    have = Counter("".join(board))
    for letter, need in Counter(word).items():
        if have[letter] < need:
            return False

    # Pruning 2: a path read backwards is the same path, so start from the
    # end whose letter is rarer on the board: fewer cells begin a search.
    if have[word[0]] > have[word[-1]]:
        word = word[::-1]

    grid = [list(row) for row in board]

    def dfs(r, c, i):
        # Can word[i:] be traced starting at cell (r, c)?
        if grid[r][c] != word[i]:
            return False
        if i == len(word) - 1:
            return True
        grid[r][c] = "#"  # mark: "#" matches no letter, so this path cannot reuse the cell
        found = False
        for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
            if 0 <= nr < rows and 0 <= nc < cols and dfs(nr, nc, i + 1):
                found = True
                break
        grid[r][c] = word[i]  # restore the letter for other paths
        return found

    for r in range(rows):
        for c in range(cols):
            if dfs(r, c, 0):
                return True
    return False

Pitfalls and edge cases

Most wrong answers come from the marking and the bounds checks.

Not unmarking a cell after a failed branch. The cell stays blocked for every later path, and on AA / AB the word AAA comes out false.
Not marking at all. Without it the path can step back onto the cell it came from, and POP on the example board would return true.
Reading the cell before checking the bounds. In Python, board[-1] is the last row, not an error, so a missing bounds check quietly wraps around the grid.
Checking for success only after a move. A one-letter word on a one-cell board, ["A"] with A, must return true even though the cell has no neighbors.
Marking with a character that can be a real letter. Swapping a cell's case, for example, breaks on boards that use both a and A.
Moving diagonally. Only the four cells that share a side count as neighbors.

Frequently asked questions4

What is the time complexity of Word Search?

The worst case is O(m·n·3^L) for an m × n board and a word of length L. Each of the m·n cells can start a path, and after the first step each cell has at most three unvisited neighbors to try. The extra space is O(L) for the recursion, plus O(m·n) if you copy the board to mark it.

Why do you unmark cells in Word Search?

A mark means the cell is on the current path. When a branch fails, the cell leaves the path, and a different path may need it. If you keep the mark, later searches treat the cell as used and can miss a valid tracing. Mark on the way in, unmark on the way out.

How does pruning make Word Search faster?

Two checks run before the search. If the word needs more of some letter than the board holds, you can return false without searching. And because a path read backwards spells the reversed word, you can start from whichever end has the rarer letter, which cuts the number of starting cells and fails wrong paths sooner. Neither changes the worst case, and the plain search is a complete answer on its own. On a 5 × 5 board of A with a word that needs a missing B, they turn roughly 65,000 cell checks into none.

What is the difference between Word Search and Word Search II?

Word Search asks about one word. Word Search II gives a list of words and asks which ones appear on the board. Running this search once per word repeats a lot of work, so the usual solution puts all the words in a trie and walks the board once, abandoning a path as soon as no word starts with its letters.

Python

def exist(board, word):
    # Write code here

Test cases

Case 1

Case 2

Case 3

Input

board = ["STAR", "POOL", "ENDS"]
word = "STOOLS"

Expected

true