word_ladder_2.java

public class PathNode {
		PathNode pre;
		String word;
		int pathLength;
		PathNode(PathNode pre, String word, int len) {
			this.pre = pre;
			this.word = word;
			this.pathLength = len;
		}
	}
	
	Set<String> uniqWords = new HashSet<String> ();
	List<List<String>> result = new ArrayList<> ();
	int shortestLen = Integer.MAX_VALUE;
	boolean isFirstPath = true;
	public List<List<String>> findLadders(String beginWord, String endWord, Set<String> wordList) {
		Deque<PathNode> queue = new ArrayDeque<>();
		queue.add(new PathNode(null, beginWord, 1));
		uniqWords.add(beginWord);
		while (!queue.isEmpty()) {
			PathNode node = queue.remove();
			if (node.pathLength > shortestLen) {
			    break;
			}
			uniqWords.add(node.word);
			if (node.word.equals(endWord) && (isFirstPath || node.pathLength == shortestLen)) {
				addOnePath(node);
			}
			for (int i = 0; i < node.word.length(); i++) {
				for(char ch = 'a'; ch < 'z'; ch++) {
					StringBuilder sb = new StringBuilder(node.word);
					if (sb.charAt(i) != ch) {
						sb.setCharAt(i, ch);
						String newWord = sb.toString();
						if (wordList.contains(newWord) && !uniqWords.contains(newWord)) {
							queue.add(new PathNode(node, newWord, node.pathLength + 1));
						}
					}
				}
			}
		}
		return result;
    }
	private void addOnePath(PathNode node) {
		if (node.pathLength < shortestLen) {
			shortestLen = node.pathLength;
			isFirstPath = false;
		}
		Deque<String> stack = new ArrayDeque<String> ();
		List<String> list = new ArrayList<> ();
		while (node != null) {
			stack.addFirst(node.word);
			node = node.pre;
		}
		while (!stack.isEmpty()) {
			list.add(stack.removeFirst());
		}
		result.add(list);
	}