Question

Formatted question description: https://leetcode.ca/all/126.html

A transformation sequence from word beginWord to word endWord using a dictionary wordList is a sequence of words beginWord -> s₁ -> s₂ -> ... -> s_k such that:

Every adjacent pair of words differs by a single letter.
Every s_i for 1 <= i <= k is in wordList. Note that beginWord does not need to be in wordList.
s_k == 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, s₁, s₂, ..., s_k].

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 10⁵.

Algorithm

This solution uses a combination of Breadth-First Search (BFS) for discovering the shortest paths and Depth-First Search (DFS) for building the actual paths, a common approach for such problems.

Here’s a step-by-step explanation of the code:

BFS Phase

Initialization: The words set contains all the words from wordList, ensuring quick lookup. If endWord is not in words, the function returns an empty list as no transformation is possible.
Distance and Predecessor Tracking: dist keeps track of the shortest distance (in terms of steps) from beginWord to any word encountered during BFS. prev is a mapping from a word to all of its predecessors on the shortest path from the beginWord.
BFS Execution: Starting from beginWord, the code iteratively transforms each letter of the current word to all possible 26 letters and checks if the new word is in words. If a new valid word is found, it’s added to the queue for further exploration, and its distance and predecessors are updated. The BFS continues until endWord is found (found = True), ensuring only the shortest paths are considered.
Key BFS Details:
- The BFS layer-by-layer processing is essential for finding the shortest path efficiently.
- When a transformation leads to a word already at the current step, it means this word can be reached through another transformation, so the current word is added as its predecessor.
- The check if dist.get(t, 0) == step ensures that only words reachable in the current number of steps are considered, which helps in identifying all predecessors of words on the shortest paths.
- Once endWord is found, the BFS search can stop, as all shortest paths to endWord would have been discovered due to the layer-by-layer nature of BFS.

DFS Phase

Building Paths: The dfs function is a recursive function that constructs paths from endWord back to beginWord using the prev mapping filled during BFS. It does so by starting with endWord and recursively exploring all its predecessors, appending each valid path to ans.
Path Construction: The path is constructed in reverse (from endWord to beginWord) because the prev mapping stores how to reach each word from the start word, making it natural to traverse the mapping in reverse to reconstruct the path. Once the path reaches beginWord, it’s reversed to match the required direction and added to ans.
Efficiency Considerations: The reason for traversing from endWord to beginWord (as noted in the comment) is to reduce the number of paths explored during DFS. Since prev contains only predecessors on the shortest paths, paths that do not lead to endWord in the minimum number of steps are naturally excluded, making the DFS phase more efficient.

Conclusion

This approach ensures that all shortest transformation sequences are found by first using BFS to discover the shortest path lengths and record predecessors, then using DFS to build the paths from these predecessors. The combination of BFS for shortest path discovery and DFS for path construction is a powerful pattern for solving similar problems in graph theory and word transformation challenges.

Code

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Set;

public class Word_Ladder_II {

	// iteration bfs
	// https://leetcode.com/problems/word-ladder-ii/solution/
    public class Solution {

        List<List<String>> list = new ArrayList<List<String>>();

        public List<List<String>> findLadders(String start, String end, Set<String> dict) {

            if (start == null || end == null || dict == null) return list;

            dict.add(end); // !!!

            Queue<String> q = new LinkedList<String>();
            int level = 1;
            int currentLevelCount = 1;
            int newLevelCount = 0;
            boolean found = false;
            int foundLevel = -1;

            // from end word, to all paths
            HashMap<String, ArrayList<ArrayList<String>>> hm = new HashMap<String, ArrayList<ArrayList<String>>>();


            q.offer(start);
            ArrayList<String> singlePath = new ArrayList<String>();
            ArrayList<ArrayList<String>> allPaths = new ArrayList<ArrayList<String>>();

            singlePath.add(start);
            allPaths.add(singlePath);
            hm.put(start, allPaths);

            while (!q.isEmpty()) {

                String current = q.poll();
                currentLevelCount--; // 这里用了新旧count来标记每个level，没有用null

                for (int i = 0; i < current.length(); i++) {
                    char[] array = current.toCharArray();

                    for (char c = 'a'; c <= 'z'; c++) {
                        array[i] = c;
                        String each = new String(array);
                        if (each.equals(end)) {
                            found = true;
                            foundLevel = level;
                        }


                        if (dict.contains(each)) {
                            // q.offer(each);
                            newLevelCount++;

                            ArrayList<ArrayList<String>> prevAllPaths = hm.get(current);

                            if (hm.containsKey(each))
                                allPaths = hm.get(each);
                            else {
                                /* @note@note:
	                                enqueue is here. if no path ending at this one, then has to explore in future
	                                if there is path ending at this one, meaning it's been explored already. no need to enqueue
	                            */
                                q.offer(each);
                                allPaths = new ArrayList<ArrayList<String>>();
                                hm.put(each, allPaths);
                            }

                            // @note@note: this if is the key !!! no path for new word, or new word path is one more than previous path
                            // using this if, the"if visited" check can be removed
                            // if (allPaths.size() == 0 || prevAllPaths.size() + 1 == allPaths.size()) {
                            if (allPaths.size() == 0 || prevAllPaths.get(0).size() + 1 == allPaths.get(0).size()) {
                                for (ArrayList<String> eachPath : prevAllPaths) {
                                    ArrayList<String> newone = new ArrayList<String>(eachPath);
                                    newone.add(each);
                                    allPaths.add(newone);
                                }
                            }
                        }
                    }
                }

                // @note@note: also the key, to make sure only find shortest
                if (found && foundLevel != level) {
                    break;
                }

                // @note: must be after trying the last word of currentLevel, then update
                if (currentLevelCount == 0) {
                    currentLevelCount = newLevelCount;
                    newLevelCount = 0;
                    level++;

                }

            }

            if (!found) {
                return list;
            }

            for (ArrayList<String> each : hm.get(end)) {
                list.add(each);
            }

            return list;

        }
    }


    public class Solution_recursion {

        private List<String> findPath(String fromWord, String toWord,
                                      Set<String> seenWords) {

            if (fromWord.equals(toWord)) {
                ArrayList<String> result = new ArrayList<>();
                result.add(toWord);
                return result;
            }

            // Find all words that you can go to from fromWord
            List<String> nextWords = getNextWords(fromWord, seenWords);
            for (String word : nextWords) {
                Set<String> newSeenWords = new HashSet<String>(seenWords);
                newSeenWords.add(word);
                List<String> subPath = findPath(word, toWord, newSeenWords);
                if (subPath != null) {
                    subPath.add(fromWord);
                    return subPath;
                }
            }

            // There wasn't a path
            return null;

        }

        private final List<String> WORDS = Arrays.asList("head", "heal",
            "teal", "tell", "tall", "tail");

        private final List<Character> ALPHA = Arrays.asList('a', 'b',
            'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n',
            'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z');

        private final HashSet<String> DICTIONARY = new HashSet<String>(
            WORDS);

        private List<String> getNextWords(String fromWord,
                                          Set<String> seenWords) {
            List<String> outList = new ArrayList<String>();
            StringBuilder builder;
            for (int i = 0; i < fromWord.length(); i++) {
                builder = new StringBuilder(fromWord);
                for (Character j : ALPHA) {
                    if (j == fromWord.charAt(i)) {
                        continue;
                    }
                    builder.setCharAt(i, j);
                    String potentialWord = builder.toString();
                    if (DICTIONARY.contains(potentialWord)
                        && !seenWords.contains(potentialWord)) {
                        outList.add(potentialWord);
                    }
                }
            }
            return outList;
        }
    }
}

//////

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();
        }
    }
}

'''
remove() same as discard()

>>> a = set([11,22,33])
>>> a.remove(22)
>>> a
{33, 11}

>>> a = set([11,22,33])
>>> a.discard(22)
>>> a
{33, 11}


>>> a=set([1,2,3])
>>> a.discard(555)
>>> a.remove(555)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
KeyError: 555
'''

class Solution:
    def findLadders(
        self, beginWord: str, endWord: str, wordList: List[str]
    ) -> List[List[str]]:
        # endWord to beginWord
        # better than begin to end, too many paths not in final result
        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
        # no exception if beginWord not in set
        words.discard(beginWord)
        dist = {beginWord: 0}
        prev = defaultdict(set)
        q = deque([beginWord])
        found = False
        step = 0
        while q and not found:
            step += 1
            for _ 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) # repeated 3 lines below
                        if t not in words: 
                        # if above '== step' met, then t must be removed from words[] from previous iterations
                            continue
                        prev[t].add(p) # repeated 3 lines above
                        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

############

from collections import deque

class Solution(object):
  def findLadders(self, beginWord, endWord, wordlist):
    """
    :type beginWord: str
    :type endWord: str
    :type wordlist: Set[str]
    :rtype: List[List[int]]
    """

    def getNbrs(src, dest, wordList):
      res = []
      for c in string.ascii_lowercase:
        for i in range(0, len(src)):
          newWord = src[:i] + c + src[i + 1:]
          if newWord == src:
            continue
          if newWord in wordList or newWord == dest:
            yield newWord

    def bfs(beginWord, endWord, wordList):
      distance = {beginWord: 0}
      queue = deque([beginWord])
      length = 0
      while queue:
        length += 1
        for k in range(0, len(queue)):
          top = queue.popleft()
          for nbr in getNbrs(top, endWord, wordList):
            if nbr not in distance:
              distance[nbr] = distance[top] + 1
              queue.append(nbr)
      return distance

    def dfs(beginWord, endWord, wordList, path, res, distance):
      if beginWord == endWord:
        res.append(path + [])
        return

      for nbr in getNbrs(beginWord, endWord, wordList):
        if distance.get(nbr, -2) + 1 == distance[beginWord]:
          path.append(nbr)
          dfs(nbr, endWord, wordList, path, res, distance)
          path.pop()

    res = []
    distance = bfs(endWord, beginWord, wordlist)
    dfs(beginWord, endWord, wordlist, [beginWord], res, distance)
    return res

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
}

126 - Word Ladder II

Question

Algorithm

BFS Phase

DFS Phase

Conclusion

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

BFS Phase

DFS Phase

Conclusion

Code

All Problems

All Solutions