Word Ladder II @Lintcode

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

Have you met this question in a real interview? 

Yes

Example

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

Return

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

这道题写起来长，但其实一点都不难。只要领悟以下几个关键点：

1 因为要找最短路径，所以果断用bfs

2 要求返回所有可能的解，所以要记录层数，直到把最短路径答案所在的那一层全部试过为止

3 每个最终解都是一个path，每个节点都指向他的上一层。所以最好自己建一个数据结构

4 用过一个中间string就把它从dict里删除，因为最短路径里不可能包含一个重复的string

另外自己写code中会碰到很多可以优化的地方，所以最好还是自己写一遍哦 ^_^

	public class Solution {
	/**
	* @param start, a string
	* @param end, a string
	* @param dict, a set of string
	* @return a list of lists of string
	*/
	public List<List<String>> findLadders(String start, String end, Set<String> dict) {
	// write your code here
	List<List<String>> res = new ArrayList<List<String>>();
	ArrayList<Cell> qualified = new ArrayList<Cell>();
	dict.add(start);
	Queue<Cell> queue = new LinkedList<Cell>();
	queue.add(new Cell(start, 0));
	int minLevel=Integer.MAX_VALUE;
	boolean found = false;
	while(!queue.isEmpty()){
	Cell cur = queue.poll();
	if(cur.level > minLevel) break;
	dict.remove(cur.word);
	char[] chars = cur.word.toCharArray();
	for(int i=0; i<chars.length; i++){
	char origin = chars[i];
	for(char c='a'; c<='z'; c++){
	chars[i] = c;
	String temp = new String(chars);
	if(temp.equals(end)){
	found = true;
	minLevel = cur.level;
	Cell solution = new Cell(temp, cur.level+1);
	solution.previous = cur;
	qualified.add(solution);
	break;
	}else if(dict.contains(temp)){
	Cell next = new Cell(temp, cur.level+1);
	next.previous = cur;
	queue.add(next);
	}
	}
	chars[i] = origin;
	}
	}
	for(Cell cell:qualified){
	ArrayList<String> list = new ArrayList<String>();
	while(cell !=null){
	list.add(0, cell.word);
	cell = cell.previous;
	}
	res.add(list);
	}
	return res;
	}
	class Cell{
	String word;
	Cell previous=null;
	int level;
	public Cell(String word, int level){
	this.word = word;
	this.level = level;
	}
	}
	}

view raw Word Ladder II.java hosted with ❤ by GitHub