Abstract / Summary

Given a board of letters and a list of words find all words that can be formed by moving through adjacent cells.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 39% (2+ million submissions).

Typical patterns to solve this problem:

• Array
• Backtracking
• Matrix
• String
• Trie

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation solves the classic “word search II” problem: given a 2-D board of characters and a list of target words, it returns all words that can be formed by connecting adjacent cells (horizontally or vertically) without re-using a cell within a single word. The algorithm combines depth-first search (DFS) with prefix pruning and hash-based lookups to keep the exploration focused on viable paths.

Core Workflow

The entry point is the findWords method. It first extracts the board dimensions, builds a set of all possible prefixes from the input word list, and stores the words themselves in a hash set for O(1) existence checks. The nested deeper function performs the recursive DFS, marking visited cells with a temporary sentinel value (".") and restoring them after the recursion unwinds. The outer loops iterate over every cell, launching a fresh DFS from each starting position.

Board Dimension Extraction

m = len(board[0])
n = len(board)

These two variables represent the column count (m) and row count (n). They are used throughout the DFS to enforce boundary checks.

Prefix Set Construction

prefix = set()
for w in words:
    for i in range(1, len(w)):
        prefix.add(w[:i])

For each word, every non-empty proper prefix is added to prefix. This enables early termination of DFS branches that cannot possibly lead to a complete word.

Word Hash Set

hashed = set(words)   # faster lookups

Storing the target words in a hash set allows constant-time membership tests and also supports removal of already discovered words to avoid duplicate results.

Recursive DFS (deeper)

def deeper(x, y, have):
    current = board[y][x]
    if current == ".":
        return

    have += current
    board[y][x] = "."   # tombstone

    if have in hashed:
        result.append(have)
        hashed.discard(have)

    if have in prefix:
        if x > 0:
            deeper(x - 1, y, have)
        if x < m - 1:
            deeper(x + 1, y, have)
        if y > 0:
            deeper(x, y - 1, have)
        if y < n - 1:
            deeper(x, y + 1, have)

    board[y][x] = current   # restore

The function receives the current coordinates (x, y) and the string accumulated so far (have). It first checks whether the cell is already marked as visited ("."). If not, it appends the cell’s character to have and temporarily replaces the board entry with the sentinel to prevent revisiting the same cell in the current path.

When have matches a word in hashed, the word is added to result and removed from hashed. The removal prevents the same word from being reported multiple times when encountered via different paths.

The crucial pruning step checks whether have is a known prefix. If it is not, the recursion stops, sparing the algorithm from exploring dead ends. When the prefix condition holds, the function recurses into the four orthogonal neighbours, respecting board boundaries using the pre-computed m and n.

Finally, the original character is restored, ensuring that subsequent DFS calls starting from other cells see the board in its original state.

Full Board Scan

for y in range(n):
    for x in range(m):
        deeper(x, y, "")

These nested loops launch a fresh DFS from every cell, guaranteeing that all possible starting positions are examined.

Edge-Case Handling

The algorithm explicitly handles several subtle conditions:

• Cell Reuse Prevention - By writing a sentinel (".") into a cell during the current DFS branch and restoring it afterward, the code guarantees that a single cell cannot contribute more than one character to the same word. The early if current == "." guard stops any attempt to reuse a visited cell.

• Duplicate Word Elimination - When a word is found, it is immediately removed from the hashed set. This ensures that subsequent DFS traversals that encounter the same word do not add it again to result, preserving uniqueness without extra bookkeeping.

• Prefix-Based Pruning - The check if have in prefix prevents the algorithm from descending into paths that cannot possibly complete a word. This avoids unnecessary recursion when the current string is already longer than any word sharing its prefix.

• Boundary Safety - The four directional recursive calls are guarded by explicit coordinate comparisons (x > 0, x < m - 1, etc.), ensuring that the algorithm never accesses indices outside the board’s limits.

• Empty or Single-Cell Boards - The dimension extraction works even when the board has a single row or column, and the boundary checks naturally handle the minimal case without special-casing.

Performance Optimizations

The code incorporates several techniques that reduce the effective search space and improve runtime:

• Hash-Based Membership Tests - Both the word list (hashed) and the prefix collection (prefix) are stored in Python set objects. Membership checks (in) on these structures execute in average constant time, making the frequent lookups inside the DFS inexpensive.

• In-Place Visitation Marking - Rather than allocating an auxiliary visited matrix for each DFS call, the algorithm reuses the board itself, temporarily overwriting a cell with a sentinel. This eliminates the overhead of creating and copying auxiliary data structures for every recursion depth.

• Early Termination via Prefix Check - By halting recursion as soon as the accumulated string ceases to be a prefix of any target word, the algorithm avoids exploring large swaths of the search tree that cannot yield results. This dramatically cuts down the number of recursive calls, especially when the word list contains relatively few long words.

• Result Deduplication through Set Removal - Removing a discovered word from hashed prevents the algorithm from re-exploring paths that would only reproduce an already found word. This reduces redundant work in later DFS branches.

• Minimal String Concatenation Overhead - The accumulated string have is built by simple concatenation (have += current). While Python strings are immutable, the depth of recursion is bounded by the maximum word length, keeping the overhead modest. Moreover, the algorithm never creates intermediate substrings beyond the current path.

Collectively, these choices enable the solution to handle typical board sizes and word lists efficiently, focusing computational effort on promising paths while keeping auxiliary memory usage low.

Imagine there is a big grid filled with letter tiles, just like the game where you hunt for hidden words. The goal is to find all the secret words written on a separate list.

To start, the code collects all the bits and pieces of the words into a special organizer so it knows which combinations of letters might turn into a full word later. It then looks at every single square on the board one by one.

When the code lands on a square, it checks the letter there and imagines it is the start of a word. It then looks at the neighbors on the left, right, top, and bottom to see if they can form a path that spells one of the words on the list.

To make sure it does not use the same letter tile twice for the same word, it puts a little temporary marker on the square it is currently using. If the path it is walking on turns into a word, it remembers that word. After exploring all the paths from that square, it removes the temporary marker so that other paths can use that letter again. It keeps doing this until every corner of the board has been checked.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: exponential
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++	Python		Java					TS
	WalkCCC	C++	Python		Java
	leetcode.ca	C++	Python		Java				Go	TS
	LeetcodeHelp	C++	Python		Java
	MemoryLimitExceeded	C++	Python
	Progiez	C++	Python		Java
github	aylei						Rust
	begeekmyfriend					C
	BigEggStudy			C#
	black-shadows	C++
	bujosa		Python
	charles-wangkai				Java
	chenyanzhe	C++
	everthis							JS
	FelixFan1122			C#
	fengvyi	C++
	gaosq0604		Python
	Garvit244		Python
	gouthampradhan				Java
	halfrost								Go
	JoshCrozier							JS
	keineahnung2345	C++
	lennylxx					C
	linouk23	C++
	lkwq007		Python
	MacJim	C++
	ruoru						Rust
	shreymehul			C#
	suxrobGM			C#
	varunu28				Java
	vli02					C
	wisdompeak	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, TypeScript
LeetcodeHelp	C++, Java, Python
MemoryLimitExceeded	Python, C++
Progiez	C++, Java, Python
aylei	Rust
begeekmyfriend	C
BigEggStudy	C#
black-shadows	C++, C++
bujosa	Python
charles-wangkai	Java
chenyanzhe	C++
everthis	JavaScript
FelixFan1122	C#
fengvyi	C++
gaosq0604	Python
Garvit244	Python
gouthampradhan	Java
halfrost	Go
JoshCrozier	JavaScript
keineahnung2345	C++
lennylxx	C
linouk23	C++
lkwq007	Python
MacJim	C++
ruoru	Rust
shreymehul	C#
suxrobGM	C#
varunu28	Java
vli02	C
wisdompeak	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality