Word Ladder II

LeetCode Q 126 - Word Ladder II

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

• Only one letter can be changed at a time
• Each transformed word must exist in the word list. Note that beginWord is not a transformed word.

Note:

• Return an empty list if there is no such transformation sequence.
• All words have the same length.
• All words contain only lowercase alphabetic characters.
• You may assume no duplicates in the word list.
• You may assume beginWord and endWord are non-empty and are not the same.

Example 1:
Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
Output:
[
[“hit”,”hot”,”dot”,”dog”,”cog”],
[“hit”,”hot”,”lot”,”log”,”cog”]
]

Example 2:
Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]
Output: []
Explanation: The endWord “cog” is not in wordList, therefore no possible transformation.

Solution : BFS + DFS

1. BFS: find the shortest distance between start and end, tracing the distance of crossing nodes from start node to end node, and store node’s next level neighbors to HashMap;
2. DFS: output paths with the same distance as the shortest distance from distance HashMap: compare if the distance of the next level node equals the distance of the current node + 1.

Code:

public List<List<String>> findLadders(String start, String end, List<String> wordList) { 
	
	Set<String> dict = new HashSet<>(wordList);
	Map<String, List<String>> neighbors = new HashMap<>();
	Map<String, Integer> distance = new HashMap<>();

	bfs(start, end, dict, neighbors, distance);

	List<List<String>> res = new ArrayList<>();
	dfs(start, end, neighbors, distance, res, new ArrayList<>());

	return res;
}

// BFS: Trace every node's distance from the start node (level by level).
private void bfs(String start, String end, Set<String> dict, Map<String, List<String>> neighbors, Map<String, Integer> distance) {
	
	for (String str: dict) neighbors.put(str, new ArrayList<>());

	Queue<String> que = new LinkedList<>();
	que.offer(start); 
	distance.put(start, 0);

	while (!que.isEmpty()) {
		int size = que.size();
		while (size-- != 0) {
			String curr = que.poll();
			int curDistance = distance.get(cur);                
			List<String> nextList = getNeighbors(cur, dict);

			for (String next: nextList) {
				neighbors.get(curr).add(next);
				if (!distance.contains(next)) { // Check if visited
					distance.put(next, curDistance + 1);
					que.offer(next);
				}
			}
		}
	}
}

// DFS: output all paths with the shortest distance.
private void dfs (String start, String end, Map<String, List<String>> neighbors, Map<String, Integer> distance, List<List<String>> res, List<String>() path) {
	if (start.equals(end)) {
		res.add(new ArrayList(path)); 
	} else {
		path.add(start);
		for (String next: neighbors.get(start)) {
			if (distance.get(next) == distance.get(start) + 1) 
				dfs(next, end, neighbors, distance, res, path);
		}
		path.remove(path.size() - 1);
	}
}

// Find all next level nodes.    
private ArrayList<String> getNeighbors(String node, Set<String> dict) {
	ArrayList<String> res = new ArrayList<String>();
	char chs[] = node.toCharArray();

	for (char ch ='a'; ch <= 'z'; ch++) {
		for (int i = 0; i < chs.length; i++) {
			if (chs[i] == ch) continue;
			char old_ch = chs[i];
			chs[i] = ch;
			if (dict.contains(String.valueOf(chs))) {
			    res.add(String.valueOf(chs));
			}
			chs[i] = old_ch;
		}

	}
	return res;
}