Word Search

Q: What is the time complexity of Word Search?

O(m·n·3^L) for an m × n board and a word of length L : every cell can start a path, and after the first step each cell has at most three unvisited neighbours. The extra space is O(L) for the recursion, plus O(m·n) for a copy of the board.

MediumBacktracking Graphs

+10

You get a grid of letters board, 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: start on any cell and step each time to the cell above, below, left or right, so the cells you visit spell word in order, never using a cell twice. Otherwise return false. Letters are case sensitive.

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 top-left S, go right to T, down to O, right to O and L, and down to the S below the L. No cell repeats.

Input: board = ["STAR", "POOL", "ENDS"]word = "POP"
Output: false
Explanation: The board has one P. After P and O you need another P, and the only one is the start cell, 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 only A, at row 0, column 2, touches neither S.

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

You have to search the paths through the grid. Backtracking grows one path a letter at a time, marking each cell while the path holds it and unmarking it on the way back, so no path reuses a cell. The search is exponential in the word's length, which a 6 × 6 board allows.

Backtracking with a visited grid

Intuition

A path that spells the first i letters continues to any neighbour that holds word[i] and is not on the path. With no such neighbour it is a dead end, and you back up.

The unmark is what makes this correct: a cell that a dead end walked over must be free for the next attempt. On AA / AB with AAA, both tries from the top left get stuck. If their cells stayed marked, the answer, bottom left then top left then top right, would be missed.

After the first move each step has at most three new directions, so the search can explore up to m·n·3^L paths. On a 5 × 5 board of A with 8 As and then a B, it makes about 53,000 cell checks before answering false.

Algorithm

Make a visited grid, all false.
dfs(r, c, i): false if (r, c) is outside the grid, visited, or not word[i]; true if i is the last index.
Otherwise mark (r, c), try the four neighbours with i+1, unmark it, and return whether any succeeded.
Return true if dfs(r, c, 0) succeeds from any cell.

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 search, with two changes. Mark cells on a copy of the board by writing #, and restore the letter on the way back. # never matches a letter of the word, so the letter check also rejects cells on the path.

Then prune. If the word needs more of some letter than the board holds, return false: that answers the all-A board with no search. A path read backwards spells the reversed word on the same cells, so searching for the reversed word gives the same answer. Start from the end whose letter is rarer on the board: fewer cells can start, and wrong starts fail at once.

With the only B in a corner between two Cs, the forward search makes about 35,000 cell checks; reversed, 27. The worst case stays O(m·n·3^L).

Algorithm

If the word needs more of any letter than the board has, return false.
If the board has more copies of word[0] than of the last letter, reverse word.
Copy the board into a grid you can change.
dfs(r, c, i): fail if the cell is not word[i]; succeed at the last index; else set it to #, try each in-bounds neighbour with i+1, restore it, and return whether any succeeded.
Return true if dfs succeeds from any cell.

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

Not unmarking a cell after a failed branch: AAA on AA / AB comes out false.
Not marking at all: the path steps back onto its last cell, and POP on the example board returns true.
Reading the cell before checking the bounds: in Python, board[-1] is the last row, so paths wrap around the grid.
Checking for success only after a move: ["A"] with A must return true.
Marking by swapping a cell's case: on ["aA"], the marked a reads as a second A, so aAA comes out true.

Frequently asked questions3

What is the time complexity of Word Search?

O(m·n·3^L) for an m × n board and a word of length L: every cell can start a path, and after the first step each cell has at most three unvisited neighbours. The extra space is O(L) for the recursion, plus O(m·n) for a copy of the board.

How does pruning make Word Search faster?

Count letters first, and return false if the board holds too few of one. Then search from the end with the rarer letter, which fewer cells can start from. Neither check changes the worst case.

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

Word Search II asks which words from a list appear on the board. Searching once per word repeats work, so the usual solution puts the words in a trie and walks the board once, abandoning a path when no word starts with its letters.

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

Test #1

Test #2

Test #3

Arguments

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

Expected Output

true