Graph - Word Ladder

Given two words beginWord and endWord, and a dictionary wordList, return the number of words in the shortest transformation sequence from beginWord to endWord such that only one letter can be changed at a time and each transformed word must exist in the wordList. Return 0 if no such sequence exists.

Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
Output: 5
Explanation: Shortest sequence: "hit" → "hot" → "dot" → "dog" → "cog", length 5.

Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]
Output: 0
Explanation: "cog" is not in wordList, so no valid sequence exists.

Model the problem as a graph where each word is a node and two nodes share an edge if they differ by exactly one character. We want the shortest path from beginWord to endWord, which BFS computes optimally.

Add all words from wordList into a HashSet for O(1) lookup.
Use BFS starting from beginWord, tracking the number of levels (transformations).
For each word dequeued, try replacing every character with 'a' to 'z'. If the resulting word is in the word set, enqueue it and remove it from the set (to avoid revisiting).
When endWord is reached, return the current level count. If the queue empties, return 0.

import java.util.*; public class WordLadder { public int ladderLength(String beginWord, String endWord, List<String> wordList) { Set<String> wordSet = new HashSet<>(wordList); if (!wordSet.contains(endWord)) return 0; Queue<String> queue = new LinkedList<>(); queue.offer(beginWord); int steps = 1; while (!queue.isEmpty()) { int size = queue.size(); for (int i = 0; i < size; i++) { String word = queue.poll(); char[] chars = word.toCharArray(); for (int j = 0; j < chars.length; j++) { char original = chars[j]; for (char c = 'a'; c <= 'z'; c++) { if (c == original) continue; chars[j] = c; String next = new String(chars); if (next.equals(endWord)) return steps + 1; if (wordSet.contains(next)) { wordSet.remove(next); queue.offer(next); } } chars[j] = original; } } steps++; } return 0; } }

Complexity Analysis:

Time complexity: O(M² × N) where M is the length of each word and N is the number of words in the list. For each of the N words we try M positions with 26 characters and constructing the new string takes O(M).
Space complexity: O(M × N) for the word set and BFS queue.