V

Algorithm Visualizer

ZHEN
Share on WeiboShare on XGitHub repositoryAuthor website
Learning ToolsAlgorithm Complexity ReferenceAlgorithm Learning Paths
Data StructuresArrayLinked ListStackQueue and DequeBinary Search TreeBinary HeapHash TableGraphTrieDisjoint Set UnionLRU CacheSkip ListSegment TreeB+ TreeBloom FilterFenwick Tree
SortingBubble SortCocktail Shaker SortBitonic SortSelection SortInsertion SortBinary Insertion SortShell SortMerge SortTop-Down Merge SortQuick SortThree-Way Quick SortDual-Pivot Quick SortHeap SortCounting SortRadix SortBucket Sort
Graph AlgorithmsDijkstra's Shortest PathKruskal's Minimum Spanning TreePrim's Minimum Spanning TreeBellman-Ford Shortest PathsTopological SortFloyd-WarshallStrongly Connected Components2-SATMaximum FlowBipartite MatchingLowest Common AncestorEulerian Path
Dynamic ProgrammingEdit Distance0/1 KnapsackUnbounded KnapsackLongest Common SubsequenceLongest Increasing SubsequenceCoin ChangeStone MergingTraveling Salesperson DPTree Dynamic ProgrammingDigit DPRerooting DP
Backtracking and SearchN-QueensSubsetsPermutationsCombination SumMaze Solving with DFSNumber of IslandsWord SearchSudoku SolverA* Search
StringsKMP String MatchingRabin-Karp String MatchingBoyer-Moore String MatchingManacher's Longest Palindromic SubstringSuffix ArrayLCP ArrayAho-Corasick AutomatonZ Function
Math and Number TheorySieve of EratosthenesLinear SieveEuclidean AlgorithmBinary ExponentiationExtended Euclidean AlgorithmChinese Remainder TheoremEuler's Totient FunctionMiller-Rabin Primality TestFast Fourier TransformPollard's Rho Factorization
Computational GeometryConvex HullRotating CalipersClosest Pair of PointsLine Segment IntersectionBentley-Ottmann Sweep Line
SearchingBinary SearchLower and Upper BoundSearch in a Rotated Sorted ArrayBinary Search on the AnswerTernary Search

Word Search

Backtrack through adjacent grid cells, match one character per depth, and restore visited cells after failure.

Core idea

Try every matching start cell, then recurse to adjacent cells for successive characters. Mark a cell while it is on the path and restore it when the branch returns.

Read the visualization

The board distinguishes the current path, rejected candidates, and restored cells. The character index shows exactly which word position each recursive depth must match.

A
B
C
E
S
F
C
S
A
D
E
E

Try this grid cell as the first character of the target word.

1function exist(board: string[][], word: string): boolean {
2 const R = board.length, C = board[0].length;
3 const dfs = (r: number, c: number, k: number): boolean => {
4 if (board[r][c] !== word[k]) return false; // letter not mismatch
5 if (k === word.length - 1) return true; // found → hit
6 const tmp = board[r][c]; board[r][c] = '#'; // found already found(found)
7 for (const [dr, dc] of [[-1,0],[1,0],[0,-1],[0,1]]) {
8 const nr = r + dr, nc = c + dc;
9 if (nr >= 0 && nr < R && nc >= 0 && nc < C &&
10 dfs(nr, nc, k + 1)) { board[r][c] = tmp; return true; }
11 }
12 board[r][c] = tmp; // backtrack, backtrack
13 return false;
14 };
15 for (let r = 0; r < R; r++)
16 for (let c = 0; c < C; c++)
17 if (dfs(r, c, 0)) return true; // from start count cell child start start point
18 return false;
19}
grid3×4 letter
target wordADEE
already matchA
current cell(0,0)='A'
path length1
1 / 11

Complexity and tradeoffs

Time: O(RC × 4^L). Space: O(L). Character checks and no-revisit rules prune the worst-case branching for word length L.

Invariant: The active path spells the matched word prefix and contains no grid cell more than once.

Where it fits

Word Search demonstrates path-local visited state. Multiple-word searches often replace repeated backtracking with a trie that prunes many prefixes together.