LeetCode 126 Word Ladder II

LeetCode 126 Word Ladder <div>

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:

<pre>Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]

Output: [ ["hit","hot","dot","dog","cog"],   ["hit","hot","lot","log","cog"] ] </pre>

Example 2:

<pre>Input: beginWord = "hit" endWord = "cog" wordList = ["hot","dot","dog","lot","log"]

Output: []

Explanation: The endWord "cog" is not in wordList, therefore no possibletransformation. </pre>

</div>

题目大意：

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

解题思路：

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

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

解题步骤：

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

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

注意事项：

1. 注意题目条件，开始词不在字典中(终结词默认在，否则无结果），要将它加入字典中且距离为1且要加入到path，Line 10。
2. 建图的邻接表，对没有边的节点也要加到邻接表，所以先对所有点赋空列表，再根据边更新值，Line 29。用defaultdict(list)可解决
3. 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=<code>O(L²)</code>产生新字符串需要L
时间复杂度为<code>O(n*L² + m*k)</code>，空间复杂度O(n)，m为答案个数, k为最短路径值，n为单词数。