LeetCode 126 Word Ladder II

LeetCode 126 Word Ladder

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

1. Only one letter can be changed at a time
2. 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 possibletransformation.

题目大意：

给定一个字典和两个单词。每次变换一个字母的得到新单词且该词要在字典中。求所有最少的变换路径。

解题思路：

更难于Leetcode 127，BFS用于找最短路径而DFS找路径，此题正是贯彻这一思想，先用BFS找出最短路径，
然后根据最短路径值找出所有路径。找BFS解的同时建图用邻接表表示Map>(这是
部分图，与解相关的图)和解集合Map(从始点到不同节点的最短距离)，这两个信息正是
Dijkistra的图输入和解。DFS从始点开始遍历邻接节点，确保沿着最短路径走，最短路径为
map.get(cur)+1=map.get(next)表示当前节点到始点距离+1=儿节点到始点距离，终止条件为找到目标节点。

在遍历所有邻接节点的时候，如果不加筛选对所有邻接节点都做DFS会造成LTE。关键是要利用BFS中所有
节点到单源的最短路径来剪枝。只需DFS最短路径上的节点，否则跳过。
利用了单源最短路径映射表distance后，不需要记录visited，因为重复的节点不会在最短路劲上。
Cache nextWords的结果。

解题步骤：

这题是最短路径题，第一时间想到BFS。这是一条典型的单源最短路径问题。

建字典。
BFS访问，得到图和单源最短路径Map，以及最短路径距离。同时建立邻接表graph[word] = neighbors，DFS时候不用再次找相邻单词
DFS求路径，按最短路径剪枝dict[neighbor] == dict[startWord] + 1。

注意事项：

注意题目条件，开始词不在字典中(终结词默认在，否则无结果），要将它加入字典中且距离为1且要加入到path，Line 10。
建图的邻接表，对没有边的节点也要加到邻接表，所以先对所有点赋空列表，再根据边更新值，Line 29。用defaultdict(list)可解决
DFS模板中去掉visited部分，因为用了最短距离distance的map来指导访问路径，所以不会存在循环的情况(否则不会是最短距离)
而且如果有visited会存在丢解，因为如果一个节点不在最短路径上先被访问就会被标记为visited，真正到最短路径上时就会返回。
DFS模板中加入if dict[neighbor] == dict[startWord] + 1来剪边。

Python代码：

def findLadders(self, beginWord: str, endWord: str, wordList: List[str]) -> List[List[int]]:
	if not beginWord or not endWord:
		return 0
	distance, graph = {}, defaultdict(list)
	for word in wordList:
		distance[word] = 0
	distance[beginWord] = 1
	self.bfs(beginWord, endWord, distance, graph, set())
	result = []
	self.dfs(graph, beginWord, endWord, [beginWord], result, distance) # remember [beginWord]
	return result

def dfs(self, graph, startWord, endWord, path, res, dict):
	if startWord == endWord:
		res.append(list(path))
		return
	'''if startWord in visited: # remember
		return
	visited.add(startWord)'''
	for neighbor in graph[startWord]:
		if dict[neighbor] == dict[startWord] + 1:
			path.append(neighbor)
			self.dfs(graph, neighbor, endWord, path, res, dict)
			path.pop()

def bfs(self, beginWord, endWord, dict, graph, visited):
	queue = deque([beginWord])
	visited.add(beginWord)
	# for key in dict.keys():  # remember
	#    graph[key] = []
	while queue:
		word = queue.popleft()
		if word == endWord:
			return dict[word]

		neighbors = self.get_next_words(word, dict)
		graph[word] = neighbors
		for neighbor in neighbors:
			if neighbor not in visited:
				queue.append(neighbor)
				visited.add(neighbor)
				dict[neighbor] = dict[word] + 1
	return 0

def get_next_words(self, word, dict):
	res = []
	for i in range(len(word)):
		for c in string.ascii_lowercase: # or use 'abcdefghijklmnopqrstuvwxyz'
			if c == word[i]:
				continue
			new_word = word[:i] + c + word[i + 1:]
			if new_word in dict:
				res.append(new_word)
	return res

Java代码：

public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
	List<String> path = new ArrayList<>();
	List<List<String>> res = new ArrayList<>();
	if(beginWord == null || endWord == null)
		return res;
	
	// This is a dict and also keeps track of distance
	Map<String, Integer> dict = getDict(wordList);
	// Make sure endWord is in the dict and can be the next word 
	//dict.put(endWord, 0);
	dict.put(beginWord, 1);
	HashMap<String, List<String>> graph = new HashMap<String, List<String>>();
	ladderLength(beginWord, endWord, dict, graph);
	path.add(beginWord);
	dfs(beginWord, endWord, dict, graph, path, res);
	return res;
}

void dfs(String cur, String endWord, Map<String, Integer> distance,
		HashMap<String, List<String>> graph, List<String> path, List<List<String>> res) {
	if(endWord.equals(cur)) {
		res.add(new ArrayList<>(path));
		return;
	}
	for(String word : graph.get(cur)) {
		path.add(word);
		if(distance.get(word) - 1 == distance.get(cur)) // use distance, resolve LTE the most important
			dfs(word, endWord, distance, graph, path, res);
		path.remove(path.size() - 1);
	}
}

// cache getNextWords
int ladderLength(String beginWord, String endWord, Map<String, Integer> dict, Map<String, List<String>> graph) {
	Set<String> visited = new HashSet<>();
	Queue<String> q = new LinkedList<>();
	q.offer(beginWord);
	visited.add(beginWord);
	for(String s : dict.keySet()) {// remember
		graph.put(s, new ArrayList<>());
	}
	while(!q.isEmpty()) {
		String word = q.poll();
		if(endWord.equals(word))
			return dict.get(word);
		
		List<String> nextWords = getNextWords(word, dict);
		graph.put(word, new ArrayList<>(nextWords));
		for(String s : nextWords) {
			if(visited.contains(s))
				continue;
			
			q.offer(s);
			visited.add(s);
			dict.put(s, dict.get(word) + 1);
		}
	}
	return 0;
}

Map<String, Integer> getDict(List<String> wordList) {
	Map<String, Integer> map = new HashMap<>();
	for(String word : wordList) {
		map.put(word, 0);
	}
	return map;
}

List<String> getNextWords(String word, Map<String, Integer> dict) {
	List<String> result = new ArrayList<>();
	for(int i = 0; i < word.length(); i++) {
		for(int j = 0; j < 26; j++) { 
			char newChar = (char)('a' + j);
			if(word.charAt(i) == newChar) // exclude itself
				continue;
			String newWord = word.substring(0, i) + 
					newChar + word.substring(i + 1, word.length());
			if(dict.containsKey(newWord))
				result.add(newWord);
			
		}
	}
	return result;
}

算法分析：

getNextWords是L26L=O(L²)产生新字符串需要L
时间复杂度为O(nL² + mk)，空间复杂度O(n)，m为答案个数, k为最短路径值，n为单词数。