126. Word Ladder II

Given two words (beginWord_and_endWord), and a dictionary's word list, find all shortest transformation sequence(s) frombeginWord_to_endWord, such that:

1. Only one letter can be changed at a time

2. Each transformed word must exist in the word list. Note that _beginWord _is _not _a transformed word.

Note:

• Return an empty list if there is no such transformation sequence.

• All words have the same length.

• All words contain only lowercase alphabetic characters.

• You may assume no duplicates in the word list.

• You may assume _beginWord _and _endWord _are non-empty and are not the same.

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.

Thoughts:

1. "Naive" Solution: Create a dictionary that maps <str word, List[List[str]]]> Solution lists. Initialize the layer[beginword] word as [[beginword]]. 1. Expanding the layer list as follows: 1. Having a childLayer which maps the layer for the next step 2. while current layer is not empty 1. for each w in layers keys: 2. if w is in the EndWord: res list record the results by taking all the elements of layer[w] 3. else for every position, flop the word w as neww. check if neww is in the wordList: add neww after every path in layer[w], add this result into childLayer[neww] 4. set layer to newLayer for the next iteration 5. remvoe all the keys from wordList that is in newlayers

2. BFS + DFS:

   1. Shortest transformation: BFS to find the shortest path between start and end

   2. Find all the transformation: DFS with backtracking to find all the answer

Code: T:O(L^3*l) ? (L as wordList length, l as word length). S:O(L^3*l)?

class Solution(object):
    def findLadders(self, beginWord, endWord, wordList):
        """
        :type beginWord: str
        :type endWord: str
        :type wordList: List[str]
        :rtype: List[List[str]]
        """
        wordList = set(wordList)
        res,layer = [], {}
        layer[beginWord] = [[beginWord]]

        while layer:
            newlayer = collections.defaultdict(list)
            for w in layer:
                if w == endWord:
                    res += [k for k in layer[w]]
                else:
                    for i in range(len(w)):
                        for c in string.ascii_lowercase:
                            neww = w[:i] + c + w[i+1:]
                            if neww in wordList:
                                newlayer[neww]+= [j + [neww] for j in layer[w]]
            wordList -= set(newlayer.keys()) # for avoiding unsupported operation between sets and list

            layer = newlayer

        return res

Code: BFS + DFS

class Solution {
    public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
        HashSet<String> dict = new HashSet<>(wordList);
        List<List<String>> res = new ArrayList<>();
        Map<String, Integer> distance = new HashMap<>();
        Map<String, ArrayList<String>> neighbors = new HashMap<>();
        ArrayList<String> solution = new ArrayList<>();
        dict.add(beginWord);
        bfs(beginWord, endWord, dict, distance, neighbors);
        dfs(beginWord, endWord, dict, distance, neighbors, solution, res);
        return res;
    }

   private void bfs(String start, String end, Set<String> dict,  Map<String, Integer> distance, Map<String, ArrayList<String>> nodeNeighbors) {
  for (String str : dict)
      nodeNeighbors.put(str, new ArrayList<String>());
  Queue<String> queue = new LinkedList<String>();
  queue.offer(start);
  distance.put(start, 0);

  while (!queue.isEmpty()) {
      int count = queue.size();
      boolean foundEnd = false;
      for (int i = 0; i < count; i++) {
          String cur = queue.poll();
          int curDistance = distance.get(cur);                
          List<String> neighbors = getNeighbors(cur, dict);

          for (String neighbor : neighbors) {
              // System.out.println(cur);
              nodeNeighbors.get(cur).add(neighbor);
              if (!distance.containsKey(neighbor)) {// Check if visited
                  distance.put(neighbor, curDistance + 1);
                  if (end.equals(neighbor))// Found the shortest path
                      foundEnd = true;
                  else
                      queue.offer(neighbor);
                  }
              }
          }

          if (foundEnd)
              break;
      }
  }


    private void dfs(String cur, String end, Set<String>dict , Map<String, Integer> distance, Map<String, ArrayList<String>> neighbors, List<String> solution, List<List<String>> res){
           solution.add(cur);
        // found end: add
        if(end.equals(cur)) res.add(new ArrayList<String> (solution));
        // not found yet: recursively calling dfs
        else{
            for(String next: neighbors.get(cur)){
                if(distance.get(next) == distance.get(cur) + 1)
                    dfs(next, end, dict, distance, neighbors, solution, res);
            }
        }
        solution.remove(solution.size() - 1);
    }

    private List<String> getNeighbors(String node, Set<String> dict){
        List<String> res = new ArrayList<>();
        char chs []  = node.toCharArray();
        for(char ch = 'a'; ch <= 'z'; ch++){
            for(int i = 0 ; i < chs.length; i++){
                char old = chs[i];
                chs[i] = ch;
                if(dict.contains(String.valueOf(chs))){
                    res.add(String.valueOf(chs));
                }
                chs[i] = old;
            }
        }

        return res;
    }

}