Pattern visualizer
Word Search
The core idea: treat every cell as a potential start of the word and explore outward only in directions where the next letter still matches — that's DFS with backtracking. A cell gets temporarily marked visited so the same cell can't be reused twice within one path (a letter can't do double duty), but the moment a path dead-ends, un-marking it frees that cell for other paths that start elsewhere. That mark-then-unmark discipline is what lets one exhaustive search safely try every route without a cell used on one failed path blocking a different path that never touched it. Animated on: 3x3 board with letters, find word "ABCCED" which exists as a path..
Matrix
Step 1: Start DFS at (row=0,col=0), flattened idx=0. Board[0][0]='A' matches word[0]='A'. Mark visited, look for 'B' (word[1]).
1FUNCTION exist(board, word):2 n = number of rows, m = number of columns3 visited = a grid of false flags, one per cell4 FUNCTION dfs(r, c, k):5 IF k equals the length of word: RETURN true (whole word matched)6 IF (r,c) is out of bounds, or already visited, or board[r][c] != word[k]: RETURN false7 mark (r,c) as visited8 res = try dfs into the up, down, left, right neighbors with k+1 (true if any succeeds)9 un-mark (r,c) as visited (backtrack)10 RETURN res11 FOR each row i:12 FOR each column j:13 IF dfs(i, j, 0) succeeds: RETURN true14 RETURN false
← / → step · space play · Home restart