Given a beginWord, an endWord, and a wordList, return the length of the shortest transformation sequence from beginWord to endWord, changing one letter at a time, with every intermediate word required to exist in wordList. Return 0 if no such sequence exists.
Example 1
Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
Output: 5
Explanation: hit -> hot -> dot -> dog -> cog, 5 words in the sequence.
Example 2
Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]
Output: 0
Explanation: endWord "cog" is not in wordList — no valid sequence exists.
1 <= beginWord.length <= 10endWord.length == beginWord.length1 <= wordList.length <= 5000Model this as a graph problem: each word is a node, and an edge connects two words that differ by exactly one letter — then the question becomes 'shortest path from beginWord to endWord.'
BFS guarantees the shortest path in this unweighted graph — the same guarantee covered generally in BFS / Level Order and applied directly here.
Generating a word's neighbors by trying every possible single-letter substitution at every position (26 letters * word length candidates) is more efficient than comparing against every word in the list pairwise.
// Conceptual brute force — DFS exploring every possible transformation path
public int ladderLengthDFSConceptual(String beginWord, String endWord, List<String> wordList) {
// DFS would explore each possible one-letter-different word from the current one,
// recursively, tracking path length, and take the minimum over ALL paths found
// that reach endWord. This is exponential — DFS explores full paths one at a time
// and has no way to guarantee the FIRST path it finds is the shortest one, so it
// would need to explore every possible path before it could be sure of the minimum.
throw new UnsupportedOperationException("Impractical — see explanation");
}Time: Exponential in the worst case · Space: O(n * L) for the recursion