Word Ladder

A transformation sequence from word beginWord to word endWord using a dictionary wordList is a sequence of words beginWord -> s1 -> s2 -> ... -> sk such that:

Every adjacent pair of words differs by a single letter. Every si for 1 <= i <= k is in wordList. Note that beginWord does not need to be in wordList. sk == endWord Given two words, beginWord and endWord, and a dictionary wordList, return the number of words in the shortest transformation sequence from beginWord to endWord, or 0 if no such sequence exists.

BFS#

Each word is a node in an implicit graph, and an edge exists between two words if they differ by exactly one letter. Asking for the shortest transformation sequence is therefore a shortest-path query on this graph — BFS is the right tool because all edges have equal weight (each step transforms exactly one character). From the current word we try replacing every character with every letter 'a'–'z' and enqueue any resulting word found in the word set (removing it from the set to prevent revisiting). The level at which BFS first reaches endWord is the length of the shortest transformation sequence. The time complexity is O(N × L × 26) where N is the size of the word list and L is the word length, because for each word we attempt 26L single-character variants and each lookup in the word set is O(L) for hashing.