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:

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.

For example,

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

Return

  [
    ["hit","hot","dot","dog","cog"],
    ["hit","hot","lot","log","cog"]
  ]

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.

UPDATE (2017/1/20):
The wordList parameter had been changed to a list of strings (instead of a set of strings). Please reload the code definition to get the latest changes.

Solution:

We first apply BFS to construct a adjacent list storing the mapping of each node and its neighbors.

In the BFS process, we also create a distance map which maps the shortest distance of each node from start.

Having these information, we can then apply DFS to add all valid path.

In each recursion step, we check if the distance of the neighbor of the current node has exactly one steps further than the current node, it is a valid candidate.



Code:

public class Solution {
    public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
        HashSet<String> dict = new HashSet<>(wordList);
        HashMap<String, Integer> distance = new HashMap<>();
        HashMap<String, List<String>> adj = new HashMap<>();
        List<List<String>> result = new ArrayList<>();
        List<String> path = new ArrayList<>();
        dict.add(beginWord);
        bfs(beginWord, endWord, dict, adj, distance);    
        path.add(beginWord);
        dfs(beginWord, endWord, result, path, dict, adj, distance);
        return result;
    }
    
    public List<String> getNeighbor(String word, HashSet<String> dict) {
        List<String> result = new ArrayList<>();
        char[] arr = word.toCharArray();
        for (char c = 'a'; c <= 'z'; c++) {
            for (int i = 0; i < arr.length; i++) {
                if (arr[i] == c) {
                    continue;
                }
                char ch = arr[i];
                arr[i] = c;
                if (dict.contains(String.valueOf(arr))) {
                    result.add(String.valueOf(arr));
                }
                arr[i] = ch;
            }
        }
        return result;
    }
    
    public void bfs(String start, 
                    String end, 
                    HashSet<String> dict, 
                    HashMap<String, List<String>> adj, 
                    HashMap<String, Integer> distance) {
        
        for (String word : dict) {
            adj.put(word, new ArrayList<String>());
        }
        
        Queue<String> queue = new LinkedList<>();
        queue.offer(start);
        distance.put(start, 0);
        while (!queue.isEmpty()) {
            String curr = queue.poll();
            int level = distance.get(curr);
            List<String> neighbor = getNeighbor(curr, dict);
            for (String nei : neighbor) {
                adj.get(curr).add(nei);
                if (!distance.containsKey(nei)) {
                    distance.put(nei, level + 1);
                    if (!end.equals(nei)) {
                        queue.offer(nei);
                    }
                }
            }
        }
    }
    
    public void dfs(String curr,
                    String end, 
                    List<List<String>> result, 
                    List<String> path, 
                    HashSet<String> dict, 
                    HashMap<String, List<String>> adj, 
                    HashMap<String, Integer> distance) {
        
        if (curr.equals(end)) {
            result.add(new ArrayList<>(path));
            return;
        }
        
        for (String nei : adj.get(curr)) {
            path.add(nei);
            if (distance.containsKey(nei) && distance.get(nei) == distance.get(curr) + 1) {
                dfs(nei, end, result, path, dict, adj, distance);
            }
            path.remove(path.size() - 1);
        }
    }
}