学步园

A general solution to the problem "find all the shortest path": for each node, use a set to store all the previous nodes in the shortest path.

import java.util.*;

public class Solution {
	

	List<List<String>> travelPath(String start, String cstr, Map<String, Set<String>> prevs_map){
		
		List<List<String>> paths = new LinkedList<List<String>>();
		
		if(start.equals(cstr))
		{
			List<String> path = new LinkedList<String>();
			path.add(start);
			paths.add(path);
			return paths;
		}
		
		Set<String> prevs = prevs_map.get(cstr);
		for(String tstr: prevs){
			
			List<List<String>> tpaths = travelPath(start, tstr, prevs_map);
			
			for(List<String> tp: tpaths)
			{
				tp.add(cstr);
				paths.add(tp);
			}
		}
		
		return paths;
	}
	
	public List<List<String>> findLadders(String start, String end, Set<String> dict) {

		dict.add(end);
		
		List<List<String>> paths = new ArrayList<List<String>>();
		
	    Map<String, Set<String>> prevs_map = new HashMap<String,Set<String>>();
	    Map<String, Integer> sdis = new HashMap<String, Integer>();
	    
	    
		Queue<Integer> dis_queue = new LinkedList<Integer>();
		Queue<String> word_queue = new LinkedList<String>();
		
		for(String tstr : dict){
			prevs_map.put(tstr, new HashSet<String>());
			sdis.put(tstr, Integer.MAX_VALUE);
		}

		
		word_queue.add(start);
		dis_queue.add(1);
		sdis.put(start, 1);

		
		int minimalLength = Integer.MAX_VALUE;
		while (word_queue.isEmpty() == false && dis_queue.peek() <= minimalLength) {
			String str = word_queue.poll();
			int dis = dis_queue.poll();
			
			if(str.equals(end))
			{
				minimalLength = dis;/////
			}
			
			int len = str.length();

			for (int i = 0; i < len; i++) {
				char[] char_arr = str.toCharArray();

				for (char c = 'a'; c <= 'z'; c++) {
					char_arr[i] = c;

					String tstr = new String(char_arr);

					if (dict.contains(tstr) == true) {
						
						int cdis = sdis.get(tstr);
						if(cdis > dis + 1)
						{
							sdis.put(tstr, dis+1);
							
							prevs_map.get(tstr).clear();
							prevs_map.get(tstr).add(str);
							
							word_queue.add(tstr);
							dis_queue.add(dis+1);
						}
						
						else if(cdis == dis + 1)
						{
							prevs_map.get(tstr).add(str);
						}
					}
				}
			}
		}
		
		if(minimalLength != Integer.MAX_VALUE)
		{
			paths = travelPath( start, end, prevs_map);

		}

		return paths;
	}
	
	
	public static void main(String[] args)
	{
		Solution sol = new Solution();
		Set<String> dict = new HashSet<String>(Arrays.asList(
				"hot","dot","dog","lot","log"));
		String start = "hit", end = "cog";
		
		List<List<String>> paths = sol.findLadders(start, end, dict);
		
		for(List<String> path : paths)
		{
			for(String str : path)
			{
				System.out.print(str+" ");
			}
			System.out.println();
		}
	}
}