DSA Word Search II

The problem

Word Search II finds every listed word hidden in a letter board. Each word follows neighbouring cells up, down, left, or right. No cell repeats inside one word.

The answer in this article is the sorted list of found words. A word that cannot be traced on the board is absent from the answer. Diagonal steps never count.

board = [
    ["C", "A", "T", "S"],
    ["D", "O", "G", "E"],
    ["B", "I", "R", "D"],
    ["F", "I", "S", "H"],
]
words = ["CAT", "CATS", "DOG", "BIRD", "FISH", "COW", "PIG", "GOAT"]
print('board rows:', len(board), 'board cols:', len(board[0]))
print('words to find:', words)

Eight words are listed. Six of them are hidden in this board. The other two, COW and PIG, are not.

Intuition: search for one word at a time

The first idea searches the board once per word. Each search starts at every cell that holds the word's first letter. The searches share no work with each other.

That waste is the trap. The words CAT and CATS share their first three letters. A per-word search traces that shared start twice, and the waste grows with every shared prefix.

words = ['CAT', 'CATS']
shared = 0
first, second = words
for a, b in zip(first, second):
    if a == b:
        shared += 1
print('words:', words)
print('shared prefix letters:', shared)
print('steps traced twice under per-word search:', shared)

A prefix is the starting part of a word. Words that share a prefix should share the walk over that prefix. One shared structure can hold that sharing, and the next sections build it.

Brute force: one board search per word

The brute force runs a depth-first search for each word on its own. A visit counter records every cell the searches enter. Found words are collected and sorted at the end.

board = [
    ['C', 'A', 'T', 'S'],
    ['D', 'O', 'G', 'E'],
    ['B', 'I', 'R', 'D'],
    ['F', 'I', 'S', 'H'],
]
words = ['CAT', 'CATS', 'DOG', 'BIRD', 'FISH', 'COW', 'PIG', 'GOAT']
visits = [0]
def find(word):
    def walk(r, c, i):
        visits[0] += 1
        if i == len(word):
            return True
        if r < 0 or r >= 4 or c < 0 or c >= 4:
            return False
        if board[r][c] != word[i]:
            return False
        saved = board[r][c]
        board[r][c] = '#'
        ok = walk(r + 1, c, i + 1) or walk(r - 1, c, i + 1) or walk(r, c + 1, i + 1) or walk(r, c - 1, i + 1)
        board[r][c] = saved
        return ok
    for r in range(4):
        for c in range(4):
            if walk(r, c, 0):
                return True
    return False
found = []
for word in words:
    if find(word):
        found.append(word)
print('found:', sorted(found))
print('cell visits:', visits[0])

The brute force finds the same six words. It pays for them with repeated walks over shared prefixes. The count grows with the number of words, even when the board stays the same.

The optimal solution: one walk guided by a trie

A trie is a tree of letters where each edge adds one letter, and walking the board while following trie edges checks every word that shares a prefix in one shared search. That one sentence is the whole method.

A board letter missing from the current trie node ends that path at once. Ending a path early in this way is called pruning the search. A dollar key in a node marks the end of a stored word.

board = [
    ["C", "A", "T", "S"],
    ["D", "O", "G", "E"],
    ["B", "I", "R", "D"],
    ["F", "I", "S", "H"],
]
words = ["CAT", "CATS", "DOG", "BIRD", "FISH", "COW", "PIG", "GOAT"]
trie = {}
nodes = [0]
def insert(word):
    node = trie
    for ch in word:
        if ch not in node:
            node[ch] = {}
            nodes[0] += 1
        node = node[ch]
    node['$'] = word
for word in words:
    insert(word)
found = []
visits = [0]
def walk(r, c, node):
    ch = board[r][c]
    if ch not in node:
        return
    visits[0] += 1
    node = node[ch]
    if '$' in node:
        found.append(node['$'])
    saved = board[r][c]
    board[r][c] = '#'
    for dr, dc in ((-1, 0), (1, 0), (0, -1), (0, 1)):
        nr, nc = r + dr, c + dc
        if 0 <= nr < 4 and 0 <= nc < 4 and board[nr][nc] != '#':
            walk(nr, nc, node)
    board[r][c] = saved
for r in range(4):
    for c in range(4):
        walk(r, c, trie)
print('trie letter nodes:', nodes[0])
print('cell visits:', visits[0])
for word in sorted(found):
    print(word)
print('found:', len(found), 'of', len(words))

The trie search finds the same six words in 20 cell visits. GOAT is found by a path that turns across rows, from G up through O and A to T. COW and PIG are correctly absent.

Walkthrough: one walk finds CAT and CATS

The walk starts at the C in the top-left corner. Each step follows one trie edge. The same path reports two words, because one word is a prefix of the other.

board = [['C', 'A', 'T', 'S']]
path = [(0, 0), (0, 1), (0, 2), (0, 3)]
spelled = ''
for r, c in path:
    spelled += board[r][c]
    print('step to column', c, 'spelled:', spelled, 'is a word:', spelled in ('CAT', 'CATS'))

The path spells CAT at column 2 and CATS at column 3. The walk does not stop at CAT. A word ending inside a longer word is reported, and the walk continues along the same path.

Complexity

The brute force repeats the board search once per word, so its time grows with the word count times the board search cost. The trie search walks the board once, and its time is bounded by the board cells times the longest word length.

The trie space is one node per distinct prefix letter across all words. The board itself needs no copy, because visited cells are marked and restored in place.

print('brute force searches: 8, one per word')
print('trie search walks: 1 shared walk')
print('trie cell visits: 20')

One walk replaces eight. The saving grows as more words share prefixes. A word list with no shared prefixes saves less, and the trie still costs only its nodes.

Edge cases and pitfalls

A cell may not repeat inside one word. The walk marks a cell while it sits on the path and restores it after. Forgetting the restore blocks later words that need that cell.

A found word can be reported twice when two paths spell it. Collecting the results and removing repeats, or clearing the end marker after a find, keeps the answer clean. The board in this article spells each found word on one path only.

board = [['A', 'B'], ['B', 'A']]
words = ['ABA', 'ABAB', 'C']
trie = {}
for word in words:
    node = trie
    for ch in word:
        node = node.setdefault(ch, {})
    node['$'] = word
found = []
def walk(r, c, node):
    ch = board[r][c]
    if ch not in node:
        return
    node = node[ch]
    if '$' in node:
        found.append(node['$'])
    saved = board[r][c]
    board[r][c] = '#'
    for dr, dc in ((-1, 0), (1, 0), (0, -1), (0, 1)):
        nr, nc = r + dr, c + dc
        if 0 <= nr < 2 and 0 <= nc < 2 and board[nr][nc] != '#':
            walk(nr, nc, node)
    board[r][c] = saved
for r in range(2):
    for c in range(2):
        walk(r, c, trie)
print('found:', sorted(set(found)))
print('empty word list board search still runs, finds nothing extra')

ABA and ABAB are both found, on paths of three and four distinct cells in the two by two board. The letter C is absent from the board, so its word is absent from the answer. No cell repeats on either found path, because the mark-and-restore rule blocks the reuse while a path is live.