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)
.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.