http://oj.leetcode.com/problems/word-ladder-ii/

word ladder II

import java.util.*;

public class Solution {
    static class Graph {
        private final Map<String, Set<String>> adjList = new HashMap<>();
        private final Set<String> EMPTY = Collections.unmodifiableSet(new HashSet<String>());

        public boolean addEdge(String vFrom, String vTo) {
            check(vFrom != null);
            check(vTo != null);
            if (!adjList.containsKey(vFrom)) {
                adjList.put(vFrom, new HashSet<String>());
            }
            return adjList.get(vFrom).add(vTo);
        }

        public int outDegree(String v) {
            check(v != null);
            return adjList.containsKey(v) ? adjList.get(v).size() : 0;
        }

        public Set<String> neighbours(String v) {
            check(v != null);
            return adjList.containsKey(v) ? adjList.get(v) : EMPTY;
        }

    }

    private static void check(boolean cond) {
        if (!cond)
            throw new IllegalArgumentException();
    }

    static class Node {
        final String v;
        final Node prev;
        final int hash;
        final int pathLength;

        public Node(String v, Node prev, int pathLength) {
            check(v != null);
            this.v = v;
            this.prev = prev;
            this.pathLength = pathLength;
            this.hash = computeHash();
        }

        private int computeHash() {
            int hash = 5;
            hash = 37 * hash + v.hashCode();
//            hash = 37 * hash + ((prev != null) ? prev.v.hashCode() * 37 : 0);
            return hash;
        }

        public Node(String v, int pathLength) {
            this(v, null, pathLength);
        }

        @Override
        public boolean equals(Object obj) {
            if (obj != null && getClass() == obj.getClass()) {
                Node o = (Node) obj;
                return o.v.equals(v); //&& ((prev != null && prev.v.equals(o.prev.v)) || (prev == null && o.prev == null));
            } else {
                return false;
            }
        }

        @Override
        public int hashCode() {
            return hash;
        }

    }

    static class Runner {
        private final String start;
        private final String end;
        private final HashSet<String> dict;
        private static final char[] ALPHABET = new char[26];

        static {
            for (int i = 0; i < 26; ++i) {
                ALPHABET[i] = (char) (i + 97);
            }
        }

        public Runner(String start, String end, HashSet<String> dict) {
            this.start = start;
            this.end = end;
            this.dict = dict;
        }

        public ArrayList<ArrayList<String>> run() {
            ArrayList<Node> res = new ArrayList<>();
            Graph g = new Graph();
            addConnections(g, start, getCandidates(start));
            addConnections(g, end, getCandidates(end));
            findPaths(g, res);
            ArrayList<ArrayList<String>> ret = new ArrayList<>();
            for (Node node : res) {
                ret.add(getPath(node));
            }
            return ret;
        }

        private void findPaths(Graph g, ArrayList<Node> res) {
            Queue<Node> queue = new LinkedList<>();
            queue.add(new Node(start, 1));

            Set<Node> visited = new HashSet<>();
            visited.add(new Node(start, 1));

            int shortestPathLength = Integer.MAX_VALUE;
            while (!queue.isEmpty()) {
                Node node = queue.remove();
                visited.add(node);

                shortestPathLength = checkPath(res, shortestPathLength, node);
                for (String v : g.neighbours(node.v)) {
                    int pathLength = node.pathLength + 1;
                    Node temp = new Node(v, node, pathLength);
                    if (pathLength <= shortestPathLength && !visited.contains(temp)) {
                        queue.add(temp);
                    }
                }
            }
        }

        private int checkPath(ArrayList<Node> res, int shortestPathLength, Node node) {
            if (node.v.equals(end)) {
                if (node.pathLength < shortestPathLength) {
                    res.clear();
                    shortestPathLength = node.pathLength;
                }
                res.add(node);
            }
            return shortestPathLength;
        }

        private ArrayList<String> getPath(Node node) {
            Stack<String> path = new Stack<>();
            while (node != null) {
                path.push(node.v);
                node = node.prev;
            }
            return new ArrayList<>(path);
        }

        private void addConnections(Graph g, String from, List<String> toList) {
            for (String to : toList) {
                g.addEdge(from, to);
                if (g.outDegree(to) == 0) { //  we have not yet processed this node
                    addConnections(g, to, getCandidates(to));
                }
            }
        }


        public List<String> getCandidates(String w) {
            StringBuilder sb = new StringBuilder(w);
            List<String> ret = new ArrayList<>();
            for (int pos = 0; pos < w.length(); pos++) {
                char skip = w.charAt(pos);
                for (char c : ALPHABET) {
                    if (c == skip) continue;
                    sb.setCharAt(pos, c);
                    String newWord = sb.toString();
                    if (dict.contains(newWord)) {
                        ret.add(newWord);
                    }
                    sb.setCharAt(pos, skip);
                }
            }
            return ret;
        }
    }

    public ArrayList<ArrayList<String>> findLadders(String start, String end, HashSet<String> dict) {
        return new Runner(start, end, dict).run();
    }
}