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.
public int ladderLength(String beginWord, String endWord, List<String> wordList) {
Set<String> dict = new HashSet<>(wordList);
if (!dict.contains(endWord)) return 0;
Queue<String> queue = new LinkedList<>();
queue.offer(beginWord);
int steps = 1;
while (!queue.isEmpty()) {
int levelSize = queue.size();
for (int i = 0; i < levelSize; i++) {
String word = queue.poll();
if (word.equals(endWord)) return steps;
char[] chars = word.toCharArray();
for (int pos = 0; pos < chars.length; pos++) {
char original = chars[pos];
for (char c = 'a'; c <= 'z'; c++) {
if (c == original) continue;
chars[pos] = c;
String candidate = new String(chars);
if (dict.contains(candidate)) {
dict.remove(candidate); // remove immediately — doubles as the 'visited' check, preventing revisits
queue.offer(candidate);
}
}
chars[pos] = original; // restore before trying the next position
}
}
steps++;
}
return 0; // queue exhausted without reaching endWord — no path exists
}Time: O(n * L^2), n = wordList size, L = word length · Space: O(n * L)