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

For each start, search with a set of used cells that every call copies with time complexity O(m · n · 3^L · L) and space complexity O(L²).

What is the optimal approach and complexity for Word Search?

One board: mark a used cell with #, try its neighbours, then put the letter back with optimal time complexity O(m · n · 3^L) and space complexity O(L).

Word Search

Q: How do you identify the pattern for Word Search?

Look for key signals in the prompt: "neighbouring cells: up, down, left, right" indicates The path moves on a grid. From each cell there are at most four moves.; "does not use the same cell twice" indicates The search must remember the cells on the current path. Here the board itself can store that.; "return true if the word exists" indicates One path is enough, so the search can stop at the first match.; "letters must match in order" indicates The depth of the search is the index in the word. A move is allowed only if the next letter matches..

Medium·LeetCode #79 Pro OnlyBasic Reinforcement

LeetCode

Problem Statement

You are given a grid of letters, board, and a string, word. Return true if the word can be spelled by a path through the grid.

Each letter comes from one cell. Each step moves to a neighbouring cell: up, down, left or right (no diagonals). A path may not use the same cell twice. Letters are case-sensitive, so a and A are different.

Input

board, an m × n grid of letters, and word, a string.

Output

true if the word can be spelled this way, otherwise false.

Example 1

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"

Output: true

The path is A (0,0), B (0,1), C (0,2), C (1,2), E (2,2), D (2,1). Each cell is used once.

Example 2

Input: same board, word = "SEE"

Output: true

The path is S (1,3), E (2,3), E (2,2).

Example 3

Input: same board, word = "ABCB"

Output: false

The second B would have to reuse the only B on the board, at (0,1).

Constraints

• 1 ≤ m, n ≤ 6, where m is the number of rows and n is the number of columns.
• 1 ≤ word.length ≤ 15
• The board and the word use only lowercase and uppercase English letters.
• Follow-up: how could search pruning make the search faster on a bigger board?

Pattern Recognition Clues

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

“neighbouring cells: up, down, left, right”

→ The path moves on a grid. From each cell there are at most four moves.

“does not use the same cell twice”

→ The search must remember the cells on the current path. Here the board itself can store that.

“return true if the word exists”

→ One path is enough, so the search can stop at the first match.

“letters must match in order”

→ The depth of the search is the index in the word. A move is allowed only if the next letter matches.

Approach Complexity Ladder

Brute Force — a fresh visited set per start, copied into every callO(m · n · 3^L · L)O(L²)

For each start, search with a set of used cells that every call copies

Optimal — mark the board in place, restore it on the way backO(m · n · 3^L)O(L)

One board: mark a used cell with #, try its neighbours, then put the letter back

Brute Force Intuition

Try every cell as the starting letter. For each start, begin with an empty set of used cells. Every call copies that set and adds its own cell before it looks at the neighbours. The copying is the expensive part.

Recognition rule for this sub-pattern:

DFS from a cell, mark it visited on the way in, unmark on the way out.

Remember this · Backtracking

Trigger

"All subsets / permutations / combinations", place items under rules (N-Queens, Sudoku), find a path in a grid.

Think

At each step, what are my choices, and how do I undo a choice?

Key question

What is my state, when is it complete, and when do I prune?

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 Backtracking translate into production architectures and low-level memory mechanics.

LLD Architecture