Word Ladder – Solution & Complexity

• Each word is a node, and there is an edge between two words if they differ by exactly one character.
• Because every edge has equal cost, shortest path means breadth-first search, not Dijkstra.

• A naive graph build compares every pair of words and connects those with Hamming distance 1. That costs O(n^2 * L).
• You can do better by generating neighbors of the current BFS word on the fly: change each character to every letter from a through z and see whether the candidate exists in a hash set.

• Put beginWord in a queue with distance 1.
• Pop words level by level. The first time you reach endWord, return that distance immediately.
• Remove or mark visited words as soon as you enqueue them so you never revisit the same node.

The BFS explores each reachable word once, and each exploration tries 26 * wordLength one-letter mutations.

• Using DFS instead of BFS and accidentally returning a non-shortest path.
• Forgetting to mark words visited when enqueuing them, which can cause exponential duplication in the queue.
• Follow-up: bidirectional BFS can shrink the search frontier dramatically on large dictionaries because it grows simultaneously from both ends.