Word Ladder 2 - Get all the ladders | K5kC

Problem

Given two words (start and end), and a dictionary, find all shortest transformation sequence(s) from start to end, such that: 1) Only one letter can be changed at a time, 2) Each intermediate word must exist in the dictionary.

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].

Examples

Example 1:

1
2
3
4
5
6
7


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:

1
2
3


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.

Note

All words have the same length.
All words contain only lowercase alphabetic characters.

Intuition

We use BFS to find the shortest path distances from the start word to every reachable word, then use DFS to backtrack and collect all shortest transformation sequences. BFS ensures we only consider shortest paths, and DFS reconstructs all valid sequences.

Approach

BFS Phase:
- Use a queue to perform BFS from beginWord.
- For each word, generate all possible one-letter transformations.
- Record the minimum distance to each word in a map.
- Stop BFS when endWord is reached at the shortest distance.
DFS Phase:
- Starting from endWord, recursively backtrack to beginWord using the distance map.
- Only move to neighbors that are exactly one step closer to beginWord.
- Collect all valid paths.
Edge Cases:
- If endWord is not in the word list, return an empty list.
- All words are assumed to be the same length and lowercase.

Code

 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


class Solution {
public:
	 vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) {
		  unordered_set<string> dict(wordList.begin(), wordList.end());
		  vector<vector<string>> ans;
		  if (!dict.count(endWord)) return ans;
		  unordered_map<string, int> dist;
		  queue<string> q;
		  q.push(beginWord);
		  dist[beginWord] = 0;
		  while (!q.empty()) {
				string w = q.front(); q.pop();
				int d = dist[w];
				for (int i = 0; i < w.size(); ++i) {
					 string nw = w;
					 for (char c = 'a'; c <= 'z'; ++c) {
						  nw[i] = c;
						  if (dict.count(nw) && !dist.count(nw)) {
								dist[nw] = d + 1;
								q.push(nw);
						  }
					 }
				}
		  }
		  if (!dist.count(endWord)) return ans;
		  vector<string> path{endWord};
		  dfs(endWord, beginWord, dist, ans, path);
		  return ans;
	 }
	 void dfs(string w, string& begin, unordered_map<string, int>& dist, vector<vector<string>>& ans, vector<string>& path) {
		  if (w == begin) {
				vector<string> p = path;
				reverse(p.begin(), p.end());
				ans.push_back(p);
				return;
		  }
		  for (int i = 0; i < w.size(); ++i) {
				string nw = w;
				for (char c = 'a'; c <= 'z'; ++c) {
					 nw[i] = c;
					 if (dist.count(nw) && dist[nw] + 1 == dist[w]) {
						  path.push_back(nw);
						  dfs(nw, begin, dist, ans, path);
						  path.pop_back();
					 }
				}
		  }
	 }
};

 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


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{}
	 q := []string{beginWord}
	 dist[beginWord] = 0
	 for len(q) > 0 {
		  w := q[0]
		  q = q[1:]
		  d := dist[w]
		  for i := 0; i < len(w); i++ {
				for c := 'a'; c <= 'z'; c++ {
					 nw := w[:i] + string(c) + w[i+1:]
					 if dict[nw] && dist[nw] == 0 && nw != beginWord {
						  dist[nw] = d + 1
						  q = append(q, nw)
					 }
				}
		  }
	 }
	 if dist[endWord] == 0 {
		  return [][]string{}
	 }
	 var ans [][]string
	 var dfs func(string, []string)
	 dfs = func(w string, path []string) {
		  if w == beginWord {
				rev := make([]string, len(path))
				for i := range path {
					 rev[i] = path[len(path)-1-i]
				}
				ans = append(ans, rev)
				return
		  }
		  for i := 0; i < len(w); i++ {
				for c := 'a'; c <= 'z'; c++ {
					 nw := w[:i] + string(c) + w[i+1:]
					 if dist[nw]+1 == dist[w] {
						  dfs(nw, append(path, nw))
					 }
				}
		  }
	 }
	 dfs(endWord, []string{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


class Solution {
	 public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
		  Set<String> dict = new HashSet<>(wordList);
		  List<List<String>> ans = new ArrayList<>();
		  if (!dict.contains(endWord)) return ans;
		  Map<String, Integer> dist = new HashMap<>();
		  Queue<String> q = new LinkedList<>();
		  q.offer(beginWord);
		  dist.put(beginWord, 0);
		  while (!q.isEmpty()) {
				String w = q.poll();
				int d = dist.get(w);
				for (int i = 0; i < w.length(); i++) {
					 char[] arr = w.toCharArray();
					 for (char c = 'a'; c <= 'z'; c++) {
						  arr[i] = c;
						  String nw = new String(arr);
						  if (dict.contains(nw) && !dist.containsKey(nw)) {
								dist.put(nw, d + 1);
								q.offer(nw);
						  }
					 }
				}
		  }
		  if (!dist.containsKey(endWord)) return ans;
		  List<String> path = new ArrayList<>();
		  path.add(endWord);
		  dfs(endWord, beginWord, dist, ans, path);
		  return ans;
	 }
	 void dfs(String w, String begin, Map<String, Integer> dist, List<List<String>> ans, List<String> path) {
		  if (w.equals(begin)) {
				List<String> p = new ArrayList<>(path);
				Collections.reverse(p);
				ans.add(p);
				return;
		  }
		  for (int i = 0; i < w.length(); i++) {
				char[] arr = w.toCharArray();
				for (char c = 'a'; c <= 'z'; c++) {
					 arr[i] = c;
					 String nw = new String(arr);
					 if (dist.containsKey(nw) && dist.get(nw) + 1 == dist.get(w)) {
						  path.add(nw);
						  dfs(nw, begin, dist, ans, path);
						  path.remove(path.size() - 1);
					 }
				}
		  }
	 }
}

 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


class Solution {
	 fun findLadders(beginWord: String, endWord: String, wordList: List<String>): List<List<String>> {
		  val dict = wordList.toHashSet()
		  val ans = mutableListOf<List<String>>()
		  if (!dict.contains(endWord)) return ans
		  val dist = mutableMapOf<String, Int>()
		  val q: Queue<String> = LinkedList()
		  q.offer(beginWord)
		  dist[beginWord] = 0
		  while (q.isNotEmpty()) {
				val w = q.poll()
				val d = dist[w]!!
				for (i in w.indices) {
					 val arr = w.toCharArray()
					 for (c in 'a'..'z') {
						  arr[i] = c
						  val nw = String(arr)
						  if (dict.contains(nw) && !dist.containsKey(nw)) {
								dist[nw] = d + 1
								q.offer(nw)
						  }
					 }
				}
		  }
		  if (!dist.containsKey(endWord)) return ans
		  fun dfs(w: String, path: MutableList<String>) {
				if (w == beginWord) {
					 ans.add(path.reversed())
					 return
				}
				for (i in w.indices) {
					 val arr = w.toCharArray()
					 for (c in 'a'..'z') {
						  arr[i] = c
						  val nw = String(arr)
						  if (dist[nw] != null && dist[nw]!! + 1 == dist[w]) {
								path.add(nw)
								dfs(nw, path)
								path.removeAt(path.size - 1)
						  }
					 }
				}
		  }
		  dfs(endWord, mutableListOf(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


class Solution:
	 def findLadders(self, beginWord: str, endWord: str, wordList: list[str]) -> list[list[str]]:
		  dict_set: set[str] = set(wordList)
		  ans: list[list[str]] = []
		  if endWord not in dict_set:
				return ans
		  dist: dict[str, int] = {}
		  q: list[str] = [beginWord]
		  dist[beginWord] = 0
		  while q:
				w = q.pop(0)
				d = dist[w]
				for i in range(len(w)):
					 for c in 'abcdefghijklmnopqrstuvwxyz':
						  nw = w[:i] + c + w[i+1:]
						  if nw in dict_set and nw not in dist:
								dist[nw] = d + 1
								q.append(nw)
		  if endWord not in dist:
				return ans
		  def dfs(w: str, path: list[str]):
				if w == beginWord:
					 ans.append(path[::-1])
					 return
				for i in range(len(w)):
					 for c in 'abcdefghijklmnopqrstuvwxyz':
						  nw = w[:i] + c + w[i+1:]
						  if nw in dist and dist[nw] + 1 == dist[w]:
								dfs(nw, path + [nw])
		  dfs(endWord, [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


struct Solution;
use std::collections::{HashSet, HashMap, VecDeque};

impl Solution {
	 pub fn find_ladders(begin_word: String, end_word: String, word_list: Vec<String>) -> Vec<Vec<String>> {
		  let dict: HashSet<_> = word_list.iter().cloned().collect();
		  let mut ans = vec![];
		  if !dict.contains(&end_word) {
				return ans;
		  }
		  let mut dist = HashMap::new();
		  let mut q = VecDeque::new();
		  q.push_back(begin_word.clone());
		  dist.insert(begin_word.clone(), 0);
		  while let Some(w) = q.pop_front() {
				let d = dist[&w];
				let w_bytes = w.as_bytes();
				for i in 0..w.len() {
					 for c in b'a'..=b'z' {
						  let mut nw = w_bytes.to_vec();
						  nw[i] = c;
						  let nw_str = String::from_utf8(nw).unwrap();
						  if dict.contains(&nw_str) && !dist.contains_key(&nw_str) {
								dist.insert(nw_str.clone(), d + 1);
								q.push_back(nw_str);
						  }
					 }
				}
		  }
		  if !dist.contains_key(&end_word) {
				return ans;
		  }
		  fn dfs(w: &str, begin: &str, dist: &HashMap<String, i32>, ans: &mut Vec<Vec<String>>, path: &mut Vec<String>) {
				if w == begin {
					 let mut rev = path.clone();
					 rev.reverse();
					 ans.push(rev);
					 return;
				}
				let w_bytes = w.as_bytes();
				for i in 0..w.len() {
					 for c in b'a'..=b'z' {
						  let mut nw = w_bytes.to_vec();
						  nw[i] = c;
						  let nw_str = String::from_utf8(nw).unwrap();
						  if let Some(&d) = dist.get(&nw_str) {
								if d + 1 == dist[w] {
									 path.push(nw_str.clone());
									 dfs(&nw_str, begin, dist, ans, path);
									 path.pop();
								}
						  }
					 }
				}
		  }
		  let mut path = vec![end_word.clone()];
		  dfs(&end_word, &begin_word, &dist, &mut ans, &mut path);
		  ans
	 }
}

Complexity

⏰ Time complexity: O(n * l^2), where n is the number of words and l is the word length.
🧺 Space complexity: O(n*l), for the dictionary, distance map, and recursion stack.

Word Ladder 2 - Get all the ladders

Problem

Examples

Note

Similar Problems

Other problems

Solution

Method 1 – BFS + DFS (Optimal)

Intuition

Approach

Code

Complexity

Problem#

Examples#

Note#

Similar Problems#

Other problems#

Solution#

Method 1 – BFS + DFS (Optimal)#

Intuition#

Approach#

Code#

Complexity#

Problem

Examples

Note

Similar Problems

Other problems

Solution

Method 1 – BFS + DFS (Optimal)

Intuition

Approach

Code

Complexity