What is the brute force approach and complexity for Word Search II?

Word Search from every cell, repeated for every word; O(W · m·n · 4^L) with time complexity O(W · m · n · 4^L) and space complexity O(L).

How do you identify the pattern for Word Search II?

Look for key signals in the prompt: "find all of these words on the board" indicates Many targets at once → one trie over the words, not one search per word.; "adjacent cells, no cell used twice" indicates A walk on a grid with backtracking: mark the cell, try the neighbours, restore the cell.; "return each word once" indicates The same word can be spelled from several start cells → record it at its node, then clear the node..

Word Search II

Hard·LeetCode #212 Pro OnlyInterview-Level

LeetCode

Problem Statement

You get a board of letters (a grid) and a list of words. Find every word from the list that you can spell on the board.

To spell a word, start on any cell whose letter is the word's first letter. Each next letter must be on a cell directly above, below, left or right of the previous cell. A cell can be used at most once in the same word.

Return all the words you can spell, in any order.

Input

board: a grid of lowercase letters. words: a list of different lowercase words.

Output

A list of every word from words that can be spelled on the board. Any order is fine.

Example 1

Input: board = [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]], words = ["oath", "pea", "eat", "rain"]

Output: ["eat", "oath"]

oath goes o → a → t → h. eat goes e → a → t. pea needs a p, and the board has none. rain needs an a next to the r, and there is none.

Example 2

Input: board = [["a","b"],["c","d"]], words = ["abcb"]

Output: []

abcb needs two bs. The board has only one b, and a cell cannot be used twice in one word.

Constraints

• The board has between 1 and 12 rows and between 1 and 12 columns.
• Every board cell holds a lowercase English letter.
• The list has between 1 and 3 · 10^4 words.
• Each word has between 1 and 10 letters, all lowercase.
• All the words in the list are different from each other.

Pattern Recognition Clues

Recognising these key signals in the problem description immediately identifies the pattern:

“find all of these words on the board”

→ Many targets at once → one trie over the words, not one search per word.

“adjacent cells, no cell used twice”

→ A walk on a grid with backtracking: mark the cell, try the neighbours, restore the cell.

“return each word once”

→ The same word can be spelled from several start cells → record it at its node, then clear the node.

Approach Complexity Ladder

Brute Force — run Word Search once for each wordO(W · m · n · 4^L)O(L)

Word Search from every cell, repeated for every word; O(W · m·n · 4^L)

Optimal — one trie, one walk per cell, cut as you goO(m · n · 4^L)O(T)

Put every word in a trie; walk the board with trie nodes; stop when the letter is not a child; cut used-up branches

Brute Force Intuition

Word Search answers one question: is this word on the board? Ask it once for every word in the list and keep the ones that pass. To check one word, try each cell as the first letter, step to neighbours that match the next letter, and mark a cell as used while it is on the current path. When the walk backs up, the cell is free again.

Recognition rule for this sub-pattern:

Combine the trie with DFS/backtracking so many words are searched at once.

Remember this · Trie

Trigger

Many words + prefix search, autocomplete, word dictionary with wildcards, maximum XOR.

Think

Do many queries share prefixes that I keep re-checking?

Key question

What does each node store (children, end-of-word, count)?

Brute2Best Pro Content

Unlock Complete Visual Walkthrough & Optimal C++

The interactive animated dry-run player, optimized C++ implementation, state invariant derivations, and edge-case breakdown for this question are part of Brute2Best Pro. The anchor question of every sub-pattern is completely free.

All 440 visual dry runs & algorithms

Interactive step-by-step playback with pointer & array state transitions

52 comprehensive LLD chapters

Interactive UML diagrams, real-world stories (Food Delivery, Trading, RPG), and practice solutions

40 C++ basics labs & hardware memory models

Vtables, byte layouts, assembly insights, and multi-threading race conditions

Production-ready C++23 source code

Modern idioms, clean contracts, time/space complexity derivations, and interview takeaways

Create Free Account Log in

First anchor question per pattern, Part 1 LLD & Module 1 C++ basics are 100% Free forever.

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Trie translate into production architectures and low-level memory mechanics.

LLD Practice

Autocomplete & Search Engine

Prefix query caching, ranking, and memory-efficient trie compaction.

Explore Track

C++ Internals

Memory Alignment & Struct Padding

Minimizing pointer overhead and cache misses across 26-ary trie nodes.

Explore Track

Design Add and Search Words Data Structure