← Back to the searching page
State-Space Search (BFS / DFS / A*)
Searching where there is no array at all: states are nodes, moves are edges. Word ladders, sliding puzzles, and route planning all live here.
What to know
- BFS guarantees fewest moves when all moves cost the same.
- A* adds a heuristic that never overestimates (admissible) to focus the search.
- Bidirectional BFS meets in the middle, roughly squaring-rooting the frontier.
- The visited set is what keeps exponential spaces tractable.
In the wild: GPS routing, puzzle solvers, robot motion planning, spell-correction suggestions.
Algorithms to reach for
BFS over states
O(states · moves)Fewest transformations (Word Ladder, LeetCode 127)
Bidirectional BFS
~O(√ of BFS)Meet-in-the-middle frontier reduction
A* with heuristic
heuristic-dependentOptimal paths expanding far fewer nodes
Practice problems — with full guides
Each problem has its own page: progressive hints, how to approach it, and the full solution.