Question

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

126. Word Ladder II

Given two words (beginWord and endWord), and a dictionary's word list,
find all shortest transformation sequence(s) from beginWord to endWord, such that:

Only one letter can be changed at a time
Each intermediate word must exist in the word list


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

Example 2:

Input:
    beginWord = "hit"
    endWord = "cog"
    wordList = ["hot","dot","dog","lot","log"]
Output: []

Explanation: The endWord "cog" is not in wordList, therefore no possible transformation.


@tag-backtracking

Algorithm

Because we want to record the path, we need to record the parent node for each node, so that at the end, we will find its parent node one by one from the end point, until we find the starting point, and then flip it and add it to the result set.

Probably the process is similar, but the difference is that when deleting a string in the dictionary, this character may be used in another path. It is like this:

A -> C -> D, B -> C -> D

They will all go through C, and both are the shortest paths. When A is searched for C, and C is deleted from the dictionary. When B is searching for a string with a distance of 1, C is no longer in the dictionary.

So what to do?

We set up a hash table to store a set of parent nodes of a string, so that C is not in the dictionary and then check the hash table to see if C is in the hash table, if it is, and the parent node level of C Same as B, then B is also added to the parent node combination of C. It can be known that the distance of the parent node set of a string from the starting point must be equal, that is, they are the shortest distance.

Finally, after traversing all the points, use DFS to find all sets from the end point forward.

Code

Java

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

```
Todo
```

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

126 - Word Ladder II

Question

Algorithm

Code

All Problems

All Solutions