Skip to content

126. Word Ladder II

DifficultyHard

Description

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 all the shortest transformation sequences from beginWord to endWord, or an empty list if no such sequence exists. Each sequence should be returned as a list of the words [beginWord, s1, s2, ..., sk].

 

Example 1:

Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
Output: [["hit","hot","dot","dog","cog"],["hit","hot","lot","log","cog"]]
Explanation: There are 2 shortest transformation sequences:
"hit" -> "hot" -> "dot" -> "dog" -> "cog"
"hit" -> "hot" -> "lot" -> "log" -> "cog"

Example 2:

Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]
Output: []
Explanation: The endWord "cog" is not in wordList, therefore there is no valid transformation sequence.

 

Constraints:

  • 1 <= beginWord.length <= 5
  • endWord.length == beginWord.length
  • 1 <= wordList.length <= 500
  • wordList[i].length == beginWord.length
  • beginWord, endWord, and wordList[i] consist of lowercase English letters.
  • beginWord != endWord
  • All the words in wordList are unique.
  • The sum of all shortest transformation sequences does not exceed 105.

Solutions

Solution 1

Thinking

We need every shortest transformation, not just the length. Words have length at most \(5\) and the list at most \(500\), so the BFS depth is small, but the number of paths can be large.

Unidirectional BFS expands level by level and records each word's predecessors. Only edges that keep the current distance are stored, so every recorded path is shortest. After the end word is reached, walk the predecessor sets backward to list them all.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
class Solution:
    def findLadders(
        self, beginWord: str, endWord: str, wordList: List[str]
    ) -> List[List[str]]:
        def dfs(path, cur):
            if cur == beginWord:
                ans.append(path[::-1])
                return
            for precursor in prev[cur]:
                path.append(precursor)
                dfs(path, precursor)
                path.pop()

        ans = []
        words = set(wordList)
        if endWord not in words:
            return ans
        words.discard(beginWord)
        dist = {beginWord: 0}
        prev = defaultdict(set)
        q = deque([beginWord])
        found = False
        step = 0
        while q and not found:
            step += 1
            for i in range(len(q), 0, -1):
                p = q.popleft()
                s = list(p)
                for i in range(len(s)):
                    ch = s[i]
                    for j in range(26):
                        s[i] = chr(ord('a') + j)
                        t = ''.join(s)
                        if dist.get(t, 0) == step:
                            prev[t].add(p)
                        if t not in words:
                            continue
                        prev[t].add(p)
                        words.discard(t)
                        q.append(t)
                        dist[t] = step
                        if endWord == t:
                            found = True
                    s[i] = ch
        if found:
            path = [endWord]
            dfs(path, endWord)
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
class Solution {
    private List<List<String>> ans;
    private Map<String, Set<String>> prev;

    public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
        ans = new ArrayList<>();
        Set<String> words = new HashSet<>(wordList);
        if (!words.contains(endWord)) {
            return ans;
        }
        words.remove(beginWord);
        Map<String, Integer> dist = new HashMap<>();
        dist.put(beginWord, 0);
        prev = new HashMap<>();
        Queue<String> q = new ArrayDeque<>();
        q.offer(beginWord);
        boolean found = false;
        int step = 0;
        while (!q.isEmpty() && !found) {
            ++step;
            for (int i = q.size(); i > 0; --i) {
                String p = q.poll();
                char[] chars = p.toCharArray();
                for (int j = 0; j < chars.length; ++j) {
                    char ch = chars[j];
                    for (char k = 'a'; k <= 'z'; ++k) {
                        chars[j] = k;
                        String t = new String(chars);
                        if (dist.getOrDefault(t, 0) == step) {
                            prev.get(t).add(p);
                        }
                        if (!words.contains(t)) {
                            continue;
                        }
                        prev.computeIfAbsent(t, key -> new HashSet<>()).add(p);
                        words.remove(t);
                        q.offer(t);
                        dist.put(t, step);
                        if (endWord.equals(t)) {
                            found = true;
                        }
                    }
                    chars[j] = ch;
                }
            }
        }
        if (found) {
            Deque<String> path = new ArrayDeque<>();
            path.add(endWord);
            dfs(path, beginWord, endWord);
        }
        return ans;
    }

    private void dfs(Deque<String> path, String beginWord, String cur) {
        if (cur.equals(beginWord)) {
            ans.add(new ArrayList<>(path));
            return;
        }
        for (String precursor : prev.get(cur)) {
            path.addFirst(precursor);
            dfs(path, beginWord, precursor);
            path.removeFirst();
        }
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
class Solution {
public:
    vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) {
        vector<vector<string>> ans;
        unordered_set<string> words(wordList.begin(), wordList.end());
        if (!words.count(endWord)) {
            return ans;
        }
        words.erase(beginWord);
        unordered_map<string, int> dist{{beginWord, 0}};
        unordered_map<string, unordered_set<string>> prev;
        queue<string> q{{beginWord}};
        bool found = false;
        int step = 0;
        while (!q.empty() && !found) {
            ++step;
            for (int i = q.size(); i > 0; --i) {
                string p = q.front();
                q.pop();
                string t = p;
                for (int j = 0; j < t.size(); ++j) {
                    char ch = t[j];
                    for (char k = 'a'; k <= 'z'; ++k) {
                        t[j] = k;
                        if (dist.count(t) && dist[t] == step) {
                            prev[t].insert(p);
                        }
                        if (!words.count(t)) {
                            continue;
                        }
                        prev[t].insert(p);
                        words.erase(t);
                        q.push(t);
                        dist[t] = step;
                        if (t == endWord) {
                            found = true;
                        }
                    }
                    t[j] = ch;
                }
            }
        }
        function<void(vector<string>&, const string&)> dfs = [&](vector<string>& path, const string& cur) {
            if (cur == beginWord) {
                ans.emplace_back(path.rbegin(), path.rend());
                return;
            }
            for (const string& precursor : prev[cur]) {
                path.push_back(precursor);
                dfs(path, precursor);
                path.pop_back();
            }
        };
        if (found) {
            vector<string> path{endWord};
            dfs(path, endWord);
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
func findLadders(beginWord string, endWord string, wordList []string) [][]string {
    var ans [][]string
    words := make(map[string]bool)
    for _, word := range wordList {
        words[word] = true
    }
    if !words[endWord] {
        return ans
    }
    words[beginWord] = false
    dist := map[string]int{beginWord: 0}
    prev := map[string]map[string]bool{}
    q := []string{beginWord}
    found := false
    step := 0
    for len(q) > 0 && !found {
        step++
        for i := len(q); i > 0; i-- {
            p := q[0]
            q = q[1:]
            chars := []byte(p)
            for j := 0; j < len(chars); j++ {
                ch := chars[j]
                for k := 'a'; k <= 'z'; k++ {
                    chars[j] = byte(k)
                    t := string(chars)
                    if v, ok := dist[t]; ok {
                        if v == step {
                            prev[t][p] = true
                        }
                    }
                    if !words[t] {
                        continue
                    }
                    if len(prev[t]) == 0 {
                        prev[t] = make(map[string]bool)
                    }
                    prev[t][p] = true
                    words[t] = false
                    q = append(q, t)
                    dist[t] = step
                    if endWord == t {
                        found = true
                    }
                }
                chars[j] = ch
            }
        }
    }
    var dfs func(path []string, begin, cur string)
    dfs = func(path []string, begin, cur string) {
        if cur == beginWord {
            cp := make([]string, len(path))
            copy(cp, path)
            ans = append(ans, cp)
            return
        }
        for k := range prev[cur] {
            path = append([]string{k}, path...)
            dfs(path, beginWord, k)
            path = path[1:]
        }
    }
    if found {
        path := []string{endWord}
        dfs(path, beginWord, endWord)
    }
    return ans
}

Comments