Word Ladder II

Given two words (start and end), and a dictionary, find all shortest transformation sequence(s) from start to end, such that:

1. Only one letter can be changed at a time.
2. Each intermediate word must exist in the dictionary.

Example:

Given:

start = "hit"

end = "cog"

dict = ["hot","dot","dog","lot","log"]

Return:

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

Solution:

We create a Node class which stores all possible conversions to current one, for example: node "cog" sotres:["log", "dog"]. This Node class also stores the distance from beggining to current, for example: node "cog" has distance 4 (four conversions are needed from "hit" to "cog").

Breadth first search is used to construct nodes for each word in dictionary including start and end words. By default, all nodes have max distance except the start. We only set it at the first visiting.

Once we have all the information, a depth first search could be used to find all shortest solutions from the end to start order.

Code:

class Node {
    List<String> path; //possible paths to reach current
    int distance; // from start to current
    public Node() {
        path = new ArrayList<>();
        distance = Integer.MAX_VALUE;
    }
}

public class Solution {

    public List<List<String>> findLadders(String start, String end, Set<String> dict) {
        List<List<String>> res = new ArrayList<>();
        List<String> path = new ArrayList<>();
        Map<String, Node> map = createNodes(start, end, dict);
        dfs(start, end, map, path, res);
        return res;
    }

    private void dfs(String start, String curt, Map<String, Node> map,
                        List<String> path, List<List<String>> res) {
        path.add(curt);
        if (curt.equals(start)) {
            Collections.reverse(path);
            res.add(new ArrayList<>(path));
            Collections.reverse(path);
        } else {
            List<String> prevs = map.get(curt).path;
            for (String x : prevs) {
                if (map.get(curt).distance - 1 == map.get(x).distance) {
                    dfs(start, x, map, path, res);
                }
            }
        }
        path.remove(path.size() - 1);
    }

    private Map<String, Node> createNodes(String start, String end, 
                                            Set<String> dict) {
        Map<String, Node> map = new HashMap<>();
        dict.add(start);
        dict.add(end);
        for (String s : dict) {
            map.put(s, new Node());
        }
        map.get(start).distance = 0;

        Queue<String> q = new LinkedList<String>();
        q.offer(start);
        while (!q.isEmpty()) {
            String curt = q.poll();
            List<String> expansion = expand(curt, dict);
            for (String next : expansion) {
                map.get(next).path.add(curt);
                if (!map.get(next).isDistance()) {
                    map.get(next).distance = map.get(curt).distance + 1;
                    q.offer(next);
                }
            }
        }
        return map;
    }

    private List<String> expand(String curt, Set<String> dict) {
        List<String> res = new ArrayList<>();
        for (int i = 0; i < curt.length(); i++) {
            for (char ch = 'a'; ch <= 'z'; ch++) {
                if (ch == curt.charAt(i)) {
                    continue;
                }
                String s = curt.substring(0, i) + ch + curt.substring(i + 1);
                if (dict.contains(s)) {
                    res.add(s);
                }
            }
        }
        return res;
    }
}