Skip to content
AI360Xpert
Back to Graphs
Hard

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.

Examples

Input:beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
Output:5
One shortest transformation sequence is "hit" -> "hot" -> "dot" -> "dog" -> "cog", which is 5 words long.
Input:beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]
Output:0
The endWord "cog" is not in wordList, therefore there is no valid transformation sequence.

Constraints

  • 1 <= beginWord.length <= 10
  • endWord.length == beginWord.length
  • 1 <= wordList.length <= 5000
  • wordList[i].length == beginWord.length
  • beginWord, endWord, and wordList[i] consist of lowercase English letters.
  • beginWord != endWord
  • All the words in wordList are unique.

Breadth-First Search (BFS)

Approach

We can treat this as finding the shortest path in an unweighted graph, which is best solved using BFS. To quickly find adjacent words, we can pre-process the wordList into an adjacency list where the keys are words with one missing character (e.g., `*ot`) and the values are all words that match that pattern (e.g., `hot`, `dot`, `lot`). We start BFS from `beginWord`. At each step, we explore all valid transformations. The first time we reach `endWord`, we have found the shortest path.

Complexity Analysis

Time Complexity
O(M^2 * N)
Space Complexity
O(M^2 * N)

M is the length of each word and N is the total number of words. Building the adjacency list takes O(M^2 * N) because for each word, we create M substrings, and creating a substring takes O(M). BFS takes O(M^2 * N) in the worst case. Space complexity is O(M^2 * N) for the adjacency list and queue.

Solution.java
class Solution {    public int ladderLength(String beginWord, String endWord, List<String> wordList) {        if (!wordList.contains(endWord)) return 0;                // Build the adjacency list with patterns        Map<String, List<String>> adj = new HashMap<>();        wordList.add(beginWord);                for (String word : wordList) {            for (int i = 0; i < word.length(); i++) {                String pattern = word.substring(0, i) + "*" + word.substring(i + 1);                adj.computeIfAbsent(pattern, k -> new ArrayList<>()).add(word);            }        }                // BFS        Queue<String> queue = new LinkedList<>();        queue.offer(beginWord);        Set<String> visited = new HashSet<>();        visited.add(beginWord);                int res = 1;        while (!queue.isEmpty()) {            int size = queue.size();                        for (int i = 0; i < size; i++) {                String word = queue.poll();                if (word.equals(endWord)) return res;                                for (int j = 0; j < word.length(); j++) {                    String pattern = word.substring(0, j) + "*" + word.substring(j + 1);                                        for (String neighbor : adj.getOrDefault(pattern, new ArrayList<>())) {                        if (!visited.contains(neighbor)) {                            visited.add(neighbor);                            queue.offer(neighbor);                        }                    }                }            }            res++;        }                return 0;    }}