Word Ladder II

Given two words (beginWord and endWord), and a dictionary's word list, find all shortest transformation sequence(s) from beginWord toendWord, such that:

1. Only one letter can be changed at a time.
2. Each intermediate word must exist in the word list.

Vertex: word.

Neighbors: where all words in dictionary could get by changing one word from src.

Shortest Path: all edges are same weight for 1 -> BFS

Recover Path: record where it comes from.

Algorithm Description

Step1: construct graph to find all neighbors. Step2: do bfs traversal for graph.

all nodes share same visiting state a node will only be generated once why ? later generated node must be higher than prev...

public void bfs (String start, String end, Map<String,List<String>> graph, Map<String,Integer> levelMap);

public void dfs(String end, String cur, List<List<String>> res,  List<String> onPath,
                Map<String,Integer> levelMap, Map<String,List<String>> graph) {
        //if levelMap.get(start) + 1 == levelMap.get(nei)), dfs on nei.
        //trick 2: base case, don't forget backtrack
        if (cur.equals(end)) {
            onPath.add(end);
            res.add(new ArrayList<String>(onPath));
            onPath.remove(onPath.size() - 1);
        }
}