Word Ladder II

Problem#

Given beginWord, endWord, and a word list, return all shortest transformation sequences where consecutive words differ by one letter and every intermediate word is in the list.

Examples#

begin = "hit", end = "cog", words = ["hot","dot","dog","lot","log","cog"] → [["hit","hot","dot","dog","cog"],["hit","hot","lot","log","cog"]]

Hints#

Hint 1

Two phases: BFS from beginWord to compute level distances; DFS from endWord backwards using only edges that decrease distance.

Approach#

BFS from beginWord building dist[word] for every word in the list. Stop after the level containing endWord.
DFS from endWord backwards (looking at words at distance dist[curr] - 1) collecting paths.

Solution#

class Solution {
public:
    vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) {
        unordered_set<string> dict(wordList.begin(), wordList.end());
        if (!dict.count(endWord)) return {};
        unordered_map<string,int> dist;
        unordered_map<string, vector<string>> parents;
        queue<string> q;
        q.push(beginWord);
        dist[beginWord] = 0;
        bool found = false;
        while (!q.empty() && !found) {
            int sz = q.size();
            unordered_set<string> level;
            for (int i = 0; i < sz; ++i) {
                string w = q.front(); q.pop();
                string s = w;
                for (int j = 0; j < (int)s.size(); ++j) {
                    char orig = s[j];
                    for (char c = 'a'; c <= 'z'; ++c) {
                        if (c == orig) continue;
                        s[j] = c;
                        if (dict.count(s) && (!dist.count(s) || dist[s] == dist[w] + 1)) {
                            if (!dist.count(s)) {
                                dist[s] = dist[w] + 1;
                                level.insert(s);
                            }
                            parents[s].push_back(w);
                            if (s == endWord) found = true;
                        }
                    }
                    s[j] = orig;
                }
            }
            for (auto& w : level) q.push(w);
        }
        vector<vector<string>> out;
        vector<string> path = {endWord};
        function<void(const string&)> dfs = [&](const string& w) {
            if (w == beginWord) {
                out.push_back({path.rbegin(), path.rend()});
                return;
            }
            for (auto& p : parents[w]) {
                path.push_back(p);
                dfs(p);
                path.pop_back();
            }
        };
        if (found) dfs(endWord);
        return out;
    }
};

func findLadders(beginWord string, endWord string, wordList []string) [][]string {
    dict := map[string]bool{}
    for _, w := range wordList {
        dict[w] = true
    }
    if !dict[endWord] {
        return [][]string{}
    }
    dist := map[string]int{beginWord: 0}
    parents := map[string][]string{}
    q := []string{beginWord}
    found := false
    for len(q) > 0 && !found {
        sz := len(q)
        level := map[string]bool{}
        for i := 0; i < sz; i++ {
            w := q[0]
            q = q[1:]
            sb := []byte(w)
            for j := 0; j < len(sb); j++ {
                orig := sb[j]
                for c := byte('a'); c <= 'z'; c++ {
                    if c == orig {
                        continue
                    }
                    sb[j] = c
                    s := string(sb)
                    if dict[s] {
                        if d, ok := dist[s]; !ok || d == dist[w]+1 {
                            if _, ok := dist[s]; !ok {
                                dist[s] = dist[w] + 1
                                level[s] = true
                            }
                            parents[s] = append(parents[s], w)
                            if s == endWord {
                                found = true
                            }
                        }
                    }
                }
                sb[j] = orig
            }
        }
        for w := range level {
            q = append(q, w)
        }
    }
    out := [][]string{}
    path := []string{endWord}
    var dfs func(w string)
    dfs = func(w string) {
        if w == beginWord {
            rev := make([]string, len(path))
            for i, v := range path {
                rev[len(path)-1-i] = v
            }
            out = append(out, rev)
            return
        }
        for _, p := range parents[w] {
            path = append(path, p)
            dfs(p)
            path = path[:len(path)-1]
        }
    }
    if found {
        dfs(endWord)
    }
    return out
}

from collections import defaultdict, deque
from typing import List

class Solution:
    def findLadders(self, beginWord: str, endWord: str, wordList: List[str]) -> List[List[str]]:
        dict_set = set(wordList)
        if endWord not in dict_set:
            return []
        dist: dict[str, int] = {beginWord: 0}
        parents: dict[str, list[str]] = defaultdict(list)
        q: deque[str] = deque([beginWord])
        found = False
        while q and not found:
            level: set[str] = set()
            for _ in range(len(q)):
                w = q.popleft()
                arr = list(w)
                for j in range(len(arr)):
                    orig = arr[j]
                    for c in 'abcdefghijklmnopqrstuvwxyz':
                        if c == orig:
                            continue
                        arr[j] = c
                        s = ''.join(arr)
                        if s in dict_set and (s not in dist or dist[s] == dist[w] + 1):
                            if s not in dist:
                                dist[s] = dist[w] + 1
                                level.add(s)
                            parents[s].append(w)
                            if s == endWord:
                                found = True
                    arr[j] = orig
            for w in level:
                q.append(w)

        out: List[List[str]] = []
        path: List[str] = [endWord]

        def dfs(w: str) -> None:
            if w == beginWord:
                out.append(path[::-1])
                return
            for p in parents[w]:
                path.append(p)
                dfs(p)
                path.pop()

        if found:
            dfs(endWord)
        return out

function findLadders(beginWord, endWord, wordList) {
    const dict = new Set(wordList);
    if (!dict.has(endWord)) return [];
    const dist = new Map([[beginWord, 0]]);
    const parents = new Map();
    let q = [beginWord];
    let found = false;
    while (q.length > 0 && !found) {
        const level = new Set();
        const next = [];
        for (const w of q) {
            const arr = w.split('');
            for (let j = 0; j < arr.length; j++) {
                const orig = arr[j];
                for (let c = 97; c <= 122; c++) {
                    const ch = String.fromCharCode(c);
                    if (ch === orig) continue;
                    arr[j] = ch;
                    const s = arr.join('');
                    if (dict.has(s) && (!dist.has(s) || dist.get(s) === dist.get(w) + 1)) {
                        if (!dist.has(s)) {
                            dist.set(s, dist.get(w) + 1);
                            level.add(s);
                        }
                        if (!parents.has(s)) parents.set(s, []);
                        parents.get(s).push(w);
                        if (s === endWord) found = true;
                    }
                }
                arr[j] = orig;
            }
        }
        for (const w of level) next.push(w);
        q = next;
    }
    const out = [];
    const path = [endWord];
    const dfs = (w) => {
        if (w === beginWord) {
            out.push([...path].reverse());
            return;
        }
        for (const p of (parents.get(w) ?? [])) {
            path.push(p);
            dfs(p);
            path.pop();
        }
    };
    if (found) dfs(endWord);
    return out;
}

class Solution {
    private Map<String, List<String>> parents = new HashMap<>();
    private List<List<String>> out = new ArrayList<>();
    private Deque<String> path = new ArrayDeque<>();
    private String beginWord;

    public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
        this.beginWord = beginWord;
        Set<String> dict = new HashSet<>(wordList);
        if (!dict.contains(endWord)) return out;
        Map<String, Integer> dist = new HashMap<>();
        dist.put(beginWord, 0);
        Deque<String> q = new ArrayDeque<>();
        q.add(beginWord);
        boolean found = false;
        while (!q.isEmpty() && !found) {
            int sz = q.size();
            Set<String> level = new HashSet<>();
            for (int i = 0; i < sz; i++) {
                String w = q.poll();
                char[] arr = w.toCharArray();
                for (int j = 0; j < arr.length; j++) {
                    char orig = arr[j];
                    for (char c = 'a'; c <= 'z'; c++) {
                        if (c == orig) continue;
                        arr[j] = c;
                        String s = new String(arr);
                        if (dict.contains(s) && (!dist.containsKey(s) || dist.get(s) == dist.get(w) + 1)) {
                            if (!dist.containsKey(s)) {
                                dist.put(s, dist.get(w) + 1);
                                level.add(s);
                            }
                            parents.computeIfAbsent(s, k -> new ArrayList<>()).add(w);
                            if (s.equals(endWord)) found = true;
                        }
                    }
                    arr[j] = orig;
                }
            }
            for (String w : level) q.add(w);
        }
        if (found) {
            path.push(endWord);
            dfs(endWord);
        }
        return out;
    }

    private void dfs(String w) {
        if (w.equals(beginWord)) {
            out.add(new ArrayList<>(path));
            return;
        }
        for (String p : parents.getOrDefault(w, Collections.emptyList())) {
            path.push(p);
            dfs(p);
            path.pop();
        }
    }
}

function findLadders(beginWord: string, endWord: string, wordList: string[]): string[][] {
    const dict = new Set<string>(wordList);
    if (!dict.has(endWord)) return [];
    const dist = new Map<string, number>([[beginWord, 0]]);
    const parents = new Map<string, string[]>();
    let q: string[] = [beginWord];
    let found = false;
    while (q.length > 0 && !found) {
        const level = new Set<string>();
        const next: string[] = [];
        for (const w of q) {
            const arr = w.split('');
            for (let j = 0; j < arr.length; j++) {
                const orig = arr[j];
                for (let c = 97; c <= 122; c++) {
                    const ch = String.fromCharCode(c);
                    if (ch === orig) continue;
                    arr[j] = ch;
                    const s = arr.join('');
                    if (dict.has(s) && (!dist.has(s) || dist.get(s) === dist.get(w)! + 1)) {
                        if (!dist.has(s)) {
                            dist.set(s, dist.get(w)! + 1);
                            level.add(s);
                        }
                        if (!parents.has(s)) parents.set(s, []);
                        parents.get(s)!.push(w);
                        if (s === endWord) found = true;
                    }
                }
                arr[j] = orig;
            }
        }
        for (const w of level) next.push(w);
        q = next;
    }
    const out: string[][] = [];
    const path: string[] = [endWord];
    const dfs = (w: string): void => {
        if (w === beginWord) {
            out.push([...path].reverse());
            return;
        }
        for (const p of (parents.get(w) ?? [])) {
            path.push(p);
            dfs(p);
            path.pop();
        }
    };
    if (found) dfs(endWord);
    return out;
}

Editorial#

BFS finds shortest distance, but enumerating all shortest paths needs a parent multimap recording every “shortest predecessor”. DFS backward from endWord walks this DAG to emit each path exactly once. The “level set” prevents adding within-level edges as parents.

Complexity#

Time: O(n * L^2 + paths * L).
Space: O(n * L).

Problem#

Examples#

Hints#

Approach#

Solution#

Editorial#

Complexity#

Concept revision#

Keyboard shortcuts

Problem#

Examples#

Hints#

Approach#

Solution#

Editorial#

Complexity#

Concept revision#

Related#