WordLadder II

WordLadderII.java

/*
Given two words (start and end), and a dictionary, find all shortest transformation sequence(s) from start to end, such that:
•Only one letter can be changed at a time
•Each intermediate word must exist in the dictionary

For example,

Given:
start = "hit"
end = "cog"
dict = ["hot","dot","dog","lot","log"]


Return

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



Note:

•All words have the same length.
•All words contain only lowercase alphabetic characters.

*/
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;

public class Solution {
    String[] f;     // map dict to string array for the purpose of using its index 
	int[] dist;     // keep the distance from start node to current node
	HashMap<String, Integer> idx;   // keep word and its array index's mapping. 
	ArrayList<ArrayList<Integer>> adj; // adjacent of every words in dictionary
	ArrayList<ArrayList<Integer>> prev; // keep tracking previous node along the path
	Queue<Integer> queue;
	
	public ArrayList<ArrayList<String>> findLadders(String start, String end, HashSet<String> dict) {
	    ArrayList<ArrayList<String>> list = new ArrayList<ArrayList<String>>();
	    if (start == null || end == null || start.length() == 0 || start.length() != end.length() || dict == null || dict.size() == 0)
	    	return list;
	    	    
	    init(start, end, dict);
	    int startIdx = idx.get(start), endIdx = idx.get(end);
	    queue.offer(startIdx);
	    dist[startIdx] = 1;
	    int minSteps = Integer.MAX_VALUE;
	    while (!queue.isEmpty()){
	    	int u = queue.poll();
	    	if (u == endIdx){
	    		minSteps = Math.min(minSteps, dist[u]);
	    		continue;
	    	}
	    	if (dist[u] == minSteps)
	    		continue;
	    	ArrayList<Integer> neighbors = adj.get(u);
	    	for (int i=0; i< neighbors.size(); i++){
	    		int v = neighbors.get(i);
	    		if (dist[v] == 0){
	    			prev.get(v).add(u);
	    			dist[v] = dist[u] + 1;
	    			queue.offer(v);
	    		}else if (dist[v] == dist[u] + 1){
	    			prev.get(v).add(u);
	    		}
	    	}
	    }
	    ArrayList<Integer> path = new ArrayList<Integer>();
	    path.add(endIdx);
	    restorePath(endIdx, startIdx, minSteps, path, list);
	    
	    return list;
	}
	
	void init(String start, String end, HashSet<String> dict){
		idx = new HashMap<String, Integer>();
		dict.add(start);
		dict.add(end);
	    f = new String[dict.size()];
	    int i = 0;
	    for (String s: dict){
	    	idx.put(s, i);
	    	f[i++] = s;
	    }
	    
		adj = new ArrayList<ArrayList<Integer>>();
		prev = new ArrayList<ArrayList<Integer>>();
		queue = new LinkedList<Integer>();
		dist = new int[f.length];
		
		for (i = 0; i<f.length; i++){
			prev.add(new ArrayList<Integer>());
			
			char[] chs = f[i].toCharArray();
			ArrayList<Integer> list = new ArrayList<Integer>();
			
			for (int j=0; j<chs.length; j++){
				char oldChar = chs[j];
				for (char c = 'a'; c <= 'z'; c++){
					if (c != oldChar){
						chs[j] = c;
						String s = new String(chs);
						if (dict.contains(s)){
							list.add(idx.get(s));
						}
					}
				}
				chs[j] = oldChar;
			}
			adj.add(list);
		}
	}
	
	void restorePath(int current, int start, int minDistance, ArrayList<Integer> path, ArrayList<ArrayList<String>> list){
		if (current == start){
			ArrayList<String> sol = new ArrayList<String>();
			for (int i=path.size()-1; i>=0; i--)
				sol.add(f[path.get(i)]);
			list.add(sol);	
			return;
		}
		ArrayList<Integer> parent = prev.get(current);
		for (Integer v : parent){
			path.add(v);
			restorePath(v, start, minDistance, path, list);
			path.remove(path.size()-1);
		}
	}
}