Word Ladder II

Hard Graphs BFS for shortest path Original on LeetCode

Reported atMicrosoftTesla

Word Ladder II is a hard graphs problem solved with the bfs for shortest path pattern. The best approach, optimal (layered bfs on words + backtracking over parents), runs in O(N · L · 26 · L + A · L) time and O(N · L + E) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (bfs over whole paths) up.

Problem

You get a beginWord, an endWord and a dictionary wordList. A ladder is a sequence of words that starts with beginWord, ends with endWord, and in which each word differs from the one before it in exactly one letter position. Every word after the first must come from wordList (beginWord itself does not need to be in the list).

Return all ladders of the smallest possible length, each as the list of its words in order. The ladders may be listed in any order. If no ladder exists, return an empty list.

Examples

Example 1

Input
beginWord = "cat", endWord = "dog", wordList = ["cot", "cog", "dot", "dog", "cat", "bat", "bog"]
Output
[["cat", "cot", "cog", "dog"], ["cat", "cot", "dot", "dog"]]
Why
Both ladders use three changes, and no shorter ladder exists. The sequences may be returned in any order.

Example 2

Input
beginWord = "ape", endWord = "man", wordList = ["apt", "opt", "oat", "mat", "man"]
Output
[["ape", "apt", "opt", "oat", "mat", "man"]]
Why
There is only one way through the list, and it needs five changes.

Example 3

Input
beginWord = "abc", endWord = "xyz", wordList = ["abz", "xbz", "xyc"]
Output
[]
Why
"xyz" is not in the word list, so no ladder can finish there.

Constraints

  • 1 <= beginWord.length <= 5, and endWord and every word in wordList have the same length.
  • 1 <= wordList.length <= 500, the words in wordList are distinct.
  • All words use lowercase English letters only; beginWord != endWord.
  • The total number of shortest ladders is at most 10^5.

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 13 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (BFS over whole paths)O(P · L · 26 · L)O(P · L)
Optimal (layered BFS on words + backtracking over parents)O(N · L · 26 · L + A · L)O(N · L + E)

1Brute force (BFS over whole paths)

TimeO(P · L · 26 · L)Every path P kept in the queue is copied and expanded with L · 26 candidate words of length L. P can grow exponentially with the ladder depth.
SpaceO(P · L)The queue stores whole paths, not words, so memory grows with the number of partial ladders.

Put complete partial ladders in the queue instead of single words. Expand a path by changing one letter of its last word in every possible way. Words used during a level are removed from the dictionary only after the whole level finishes, so several paths of equal length can still reach the same word. Stop after the first level that reaches endWord.

  1. If endWord is not in the dictionary, return [].
  2. Queue starts with [beginWord]; remove beginWord from the dictionary.
  3. For each level: for each path, try every one-letter change of its last word that is still in the dictionary; extend the path, add it to the answer if it ends at endWord, else enqueue it. Track words used this level.
  4. After the level, remove the used words; stop once an answer was found.
class Solution {
    public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
        Set<String> dict = new HashSet<>(wordList);
        List<List<String>> res = new ArrayList<>();
        if (!dict.contains(endWord)) return res;
        ArrayDeque<List<String>> q = new ArrayDeque<>();
        List<String> start = new ArrayList<>();
        start.add(beginWord);
        q.add(start);
        dict.remove(beginWord);
        boolean found = false;
        while (!q.isEmpty() && !found) {
            Set<String> used = new HashSet<>();
            for (int size = q.size(); size > 0; size--) {
                List<String> path = q.poll();
                char[] arr = path.get(path.size() - 1).toCharArray();
                for (int i = 0; i < arr.length; i++) {
                    char orig = arr[i];
                    for (char c = 'a'; c <= 'z'; c++) {
                        if (c == orig) continue;
                        arr[i] = c;
                        String next = new String(arr);
                        if (!dict.contains(next)) continue;
                        used.add(next);
                        List<String> extended = new ArrayList<>(path);
                        extended.add(next);
                        if (next.equals(endWord)) {
                            found = true;
                            res.add(extended);
                        } else {
                            q.add(extended);
                        }
                    }
                    arr[i] = orig;
                }
            }
            dict.removeAll(used);
        }
        return res;
    }
}

2Optimal (layered BFS on words + backtracking over parents)

TimeO(N · L · 26 · L + A · L)Each of the N words is expanded once with L · 26 candidates of length L; then each of the A answer ladders (length ≤ N) is built once.
SpaceO(N · L + E)The dictionary, the BFS levels and the parent lists (E recorded parent edges); answers are extra.

Run a BFS on single words, one level at a time. Before expanding a level, delete its words from the dictionary so nothing goes backwards or sideways. When a word of the next level is generated from a word w, record w as one of its parents. Stop after the level that contains endWord. Every shortest ladder is now a chain of parent links from endWord back to beginWord, so a DFS over the parent lists produces each ladder exactly once.

  1. If endWord is not in the dictionary, return [].
  2. level = {beginWord}. While level is non-empty and endWord not reached: remove level's words from the dictionary; for each word and each one-letter change still in the dictionary, add the change to next and append the word to parents[change].
  3. If endWord was never reached, return [].
  4. DFS from endWord: push the word; at beginWord, add the reversed path to the answer; otherwise recurse into each parent; pop.
class Solution {
    public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
        Set<String> dict = new HashSet<>(wordList);
        List<List<String>> res = new ArrayList<>();
        if (!dict.contains(endWord)) return res;
        Map<String, List<String>> parents = new HashMap<>();
        Set<String> level = new HashSet<>();
        level.add(beginWord);
        boolean found = false;
        while (!level.isEmpty() && !found) {
            dict.removeAll(level);
            Set<String> next = new HashSet<>();
            for (String word : level) {
                char[] arr = word.toCharArray();
                for (int i = 0; i < arr.length; i++) {
                    char orig = arr[i];
                    for (char c = 'a'; c <= 'z'; c++) {
                        if (c == orig) continue;
                        arr[i] = c;
                        String cand = new String(arr);
                        if (!dict.contains(cand)) continue;
                        next.add(cand);
                        parents.computeIfAbsent(cand, k -> new ArrayList<>()).add(word);
                        if (cand.equals(endWord)) found = true;
                    }
                    arr[i] = orig;
                }
            }
            level = next;
        }
        if (!found) return res;
        List<String> path = new ArrayList<>();
        path.add(endWord);
        backtrack(endWord, beginWord, parents, path, res);
        return res;
    }

    private void backtrack(String word, String beginWord, Map<String, List<String>> parents,
                           List<String> path, List<List<String>> res) {
        if (word.equals(beginWord)) {
            List<String> ladder = new ArrayList<>(path);
            Collections.reverse(ladder);
            res.add(ladder);
            return;
        }
        for (String p : parents.get(word)) {
            path.add(p);
            backtrack(p, beginWord, parents, path, res);
            path.remove(path.size() - 1);
        }
    }
}

Edge cases to test

  • endWord missing from the list (answer is empty)
  • beginWord itself appears in the list
  • endWord is one change away from beginWord (a single two-word ladder)
  • Many ladders that share prefixes and merge again (counting paths, not words)
  • Words of length 1

Hints

Hint 1

Shortest means BFS. The ladder length is the BFS level at which endWord is first reached.

Hint 2

A word may be reached from several words of the previous level. Only edges from level k to level k+1 can lie on a shortest ladder.

Hint 3

Do the BFS on words, not on whole paths: record for each word the list of words in the previous level that lead to it. Then rebuild every ladder by backtracking from endWord through these parent lists.

FAQ

What is the best time complexity for Word Ladder II?

Optimal (layered BFS on words + backtracking over parents) runs in O(N · L · 26 · L + A · L) time and O(N · L + E) extra space. Each of the N words is expanded once with L · 26 candidates of length L; then each of the A answer ladders (length ≤ N) is built once.

Which pattern does Word Ladder II use?

It is a graphs problem that uses the bfs for shortest path pattern. Other problems with the same pattern: Shortest Path in Binary Matrix, Word Ladder, Bus Routes.

Is there a brute force solution for Word Ladder II?

Yes. Brute force (BFS over whole paths) takes O(P · L · 26 · L) time and O(P · L) space. Put complete partial ladders in the queue instead of single words.

Which edge cases should I test for Word Ladder II?

endWord missing from the list (answer is empty); beginWord itself appears in the list; endWord is one change away from beginWord (a single two-word ladder); Many ladders that share prefixes and merge again (counting paths, not words); Words of length 1.