Leetcode 126. Word Ladder II

Problem Explanation:

The problem is asking to find all the shortest paths from the beginWord to the endWord by transforming one word at a time and each transformation should exist in the wordList. Both the beginWord and endWord are given and differ from each other. The transformation sequence is valid only if the endWord is in wordList. If the endWord is not in wordList, no valid transformations exist and an empty list is returned.

The transformation occurs one letter at a time. Each transformed word should exist in the wordList and the beginWord is not a transformed word. It is also mentioned that all words have the same length and are lowercase alphabetic characters and the wordList doesn't have duplicates.

For instance, if beginWord, endWord and wordList are "hit", "cog" and ["hot","dot","dog","lot","log","cog"] respectively, the possible transformations are:

[ ["hit","hot","dot","dog","cog"], ["hit","hot","lot","log","cog"] ] The transformation from "hit" to "hot" changes one letter, and the same for each other step.

Solution Approach

The solution uses a breadth-first search (BFS) algorithm to find the shortest length from beginWord to endWord. It also builds a graph that contains all possible transformations at that level.

After that, the solution starts a iterative depth-first search (DFS) from beginWord to endWord using the graph. Each time a transformation is made, the transformed word is added into the current path. When endWord is reached, the path is pushed into the result list and the search returns.

Python Solution

1
2python
3from collections import deque, defaultdict
4class Solution:
5    def findLadders(self, beginWord, endWord, wordList):
6        
7        # Step 0: Create convenience data structures
8        wordSet = set(wordList)  # Transform list to set for quicker lookup
9        wordSet.add(beginWord)  # Add start word to our set
10        level = {word: 0 for word in wordSet}  # Visitation dictionary
11        neighbors = defaultdict(list)  # Our adjacency "graph"
12        all_combinations = defaultdict(list)  # Mapping of intermediate words and the original words
13
14        # Step 1: Perform BFS
15        self._bfs(beginWord, endWord, wordSet, level, neighbors, all_combinations)
16
17        # Step 2: Perform DFS
18        res = []
19        self._dfs(beginWord, endWord, level, neighbors, [beginWord], res)
20        
21        return res
22
23    def _bfs(self, beginWord, endWord, wordSet, level, neighbors, all_combinations):
24        queue = deque([(beginWord, 1)])  # queue with word and level
25        while queue:
26            curr_word, curr_level = queue.popleft()
27            for i in range(len(beginWord)):
28                intermediate_word = f'{curr_word[:i]}*{curr_word[i+1:]}'  # intermediate word
29                all_combinations[intermediate_word].append(curr_word)
30                if curr_word != endWord:  # if not the final word, add neighbors
31                    for word in all_combinations[intermediate_word]:
32                        if level[word] == 0:
33                            queue.append((word, curr_level+1))
34                            level[word] = curr_level+1
35                            neighbors[curr_word].append(word)
36
37    def _dfs(self, curr_word, end_word, level, neighbors, path, res):
38        if curr_word == end_word:  # finalize and add path to results
39            res.append(path)
40        for neighbor in neighbors[curr_word]:
41            if level[neighbor] - level[curr_word] == 1:  # check if we're getting closer
42                self._dfs(neighbor, end_word, level, neighbors, path+[neighbor], res)  # recurse

This Python solution firstly builds a graph with BFS and then finds all shortest paths with DFS. The time complexity is O(n^2), where n is the number of words, and the space complexity is O(n). The algorithm is suitable for this problem since it ensures to find all shortest paths efficiently.### JavaScript Solution

JavaScript solution can also be achieved using BFS to construct a graph and DFS to retrieve all paths.

1
2javascript
3class Solution {
4    findLadders(beginWord, endWord, wordList) {
5        let wordSet = new Set(wordList);
6        wordSet.add(beginWord);
7        let level = new Map();
8        let neighbors = new Map();
9
10        for (let word of wordSet) {
11            level.set(word, 0);
12            neighbors.set(word, []);
13        }
14
15        this.bfs(beginWord, endWord, wordSet, level, neighbors);
16        let res = [];
17        this.dfs(beginWord, endWord, level, neighbors, [beginWord], res);
18        return res;
19    }
20
21    bfs(beginWord, endWord, wordSet, level, neighbors) {
22        let queue = [[beginWord, 1]];
23        while (queue.length > 0) {
24            let [curr_word, curr_level] = queue.shift();
25            for (let i = 0; i < beginWord.length; i++) {
26                for (let j = 0; j < 26; j++) {
27                    let next_word = curr_word.slice(0, i) + String.fromCharCode(97 + j) + curr_word.slice(i + 1);
28                    if (!wordSet.has(next_word)) continue;
29                    if (level.get(next_word) === 0) {
30                        queue.push([next_word, curr_level + 1]);
31                        level.set(next_word, curr_level + 1);
32                    }
33                    if (level.get(next_word) === curr_level + 1) {
34                        neighbors.get(curr_word).push(next_word);
35                    }
36                }
37            }
38        }
39    }
40
41    dfs(beginWord, endWord, level, neighbors, path, res) {
42        if (beginWord === endWord) {
43            res.push(path);
44            return;
45        }
46        for (let next_word of neighbors.get(beginWord)) {
47            if (level.get(next_word) === level.get(beginWord) + 1) {
48                this.dfs(next_word, endWord, level, neighbors, [...path, next_word], res);
49            }
50        }
51    }
52}

The JavaScript solution uses the same algorithm as Python. The time complexity is O(n^2) where n is the number of words and the space complexity is O(n).

Java Solution

The following is a Java solution for the problem:

1
2java
3class Solution {
4    public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
5        Set<String> wordSet = new HashSet<>(wordList);
6        List<List<String>> res = new ArrayList<>();
7        Map<String, ArrayList<String>> nodeNeighbors = new HashMap<>();
8        Map<String, Integer> distance = new HashMap<>();
9        ArrayList<String> solution = new ArrayList<>();
10
11        wordSet.add(beginWord);
12        bfs(beginWord, endWord, wordSet, nodeNeighbors, distance);
13        dfs(beginWord, endWord, nodeNeighbors, distance, solution, res);
14        return res;
15    }
16
17    private void bfs(String start, String end, Set<String> dict, Map<String, ArrayList<String>> nodeNeighbors, Map<String, Integer> distance) {
18        for (String str : dict)
19            nodeNeighbors.put(str, new ArrayList<>());
20
21        Queue<String> queue = new LinkedList<>();
22        queue.offer(start);
23        distance.put(start, 0);
24
25        while (!queue.isEmpty()) {
26            int count = queue.size();
27            boolean foundEnd = false;
28            for (int i = 0; i < count; i++) {
29                String cur = queue.poll();
30                int curDistance = distance.get(cur);
31                ArrayList<String> neighbors = getNeighbors(cur, dict);
32
33                for (String neighbor : neighbors) {
34                    if (!distance.containsKey(neighbor)) {
35                        distance.put(neighbor, curDistance + 1);
36                        if (end.equals(neighbor))
37                            foundEnd = true;
38                        else
39                            queue.offer(neighbor);
40                    }
41
42                    nodeNeighbors.get(cur).add(neighbor);
43                }
44            }
45
46            if (foundEnd)
47                break;
48        }
49    }
50
51    private ArrayList<String> getNeighbors(String node, Set<String> dict) {
52        ArrayList<String> res = new ArrayList<>();
53        char chs[] = node.toCharArray();
54
55        for (char ch = 'a'; ch <= 'z'; ch++) {
56            for (int i = 0; i < chs.length; i++) {
57                if (chs[i] == ch)
58                    continue;
59
60                char old_ch = chs[i];
61                chs[i] = ch;
62                
63                if (dict.contains(String.valueOf(chs))) {
64                    res.add(String.valueOf(chs));
65                }
66
67                chs[i] = old_ch;
68            }
69        }
70        return res;
71    }
72
73    private void dfs(String cur, String end, Map<String, ArrayList<String>> nodeNeighbors, Map<String, Integer> distance, ArrayList<String> solution, List<List<String>> res) {
74        solution.add(cur);
75        if (end.equals(cur)) {
76            res.add(new ArrayList<String>(solution));
77        } else {
78            for (String next : nodeNeighbors.get(cur)) {
79                if (distance.get(next) == distance.get(cur) + 1) {
80                    dfs(next, end, nodeNeighbors, distance, solution, res);
81                }
82            }
83        }
84
85        solution.remove(solution.size() - 1);
86    }
87}

This Java solution uses a similar BFS and DFS pattern as the previous solutions. It first performs a BFS and prepares the adjacency list and distance mapping. Then it carries out a DFS to collect all the possible shortest paths into a resulting list. The time complexity is O(n^2) where n is the number of words and the space complexity is O(n).