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

To record the path, we need to track the parent node for each node. We start from the end point and find its parent node one by one until we find the starting point. Then we flip the path and add it to the result set.

The process is similar to finding the shortest path in a dictionary of words, but with a key difference. When deleting a string from the dictionary, the deleted character may still be used in another path. For example, both "A -> C -> D" and "B -> C -> D" use the letter “C” and are both shortest paths.

When we delete “C” from the dictionary, we need to find a way to continue searching for paths that use “C”. We can set up a hash table to store a set of parent nodes for each string. If “C” is not in the dictionary but appears in the hash table, we check if the parent node level of “C” is the same as that of the current node “B”. If they are the same, we add “B” to the parent node combination of “C”. This ensures that the parent node set of a string from the starting point must have the same shortest distance.

After traversing all the nodes, we use DFS to find all sets of parent nodes from the end point forward.

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

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Code

All Problems

All Solutions