LeetCode 127 Word Ladder

LeetCode 127 Word Ladder

<div>

Given two words (beginWord and endWord), and a dictionary's word list, find the length of shortest transformation sequence 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:

• Return 0 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: 5

Explanation: As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog", return its length 5. </pre>

Example 2:

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

Output: 0

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

</div>

题目大意：

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

解题思路：

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

1. 这是图，所以要有visited记录是否重复访问。
2. 字典的实现两个作用： 快速查找，以及记录距离可以省下一轮循环。总共两重循环。
3. getNextWords的实现。通过变换每位上字母，比较巧妙。

解题步骤：

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

1. 建字典。
2. BFS访问。
3. 求所有距离为1的相邻单词getNextWords。

注意事项：

1. 注意题目条件，开始词不在字典中(终结词默认在，否则无结果），要将它加入字典中且距离为1。
2. 用Map来记录解(儿子节点，参考按层搜索)，visited用于记录父节点
3. getNextWords的实现不含自己。
4. Python中用popleft出列，不是pop

Python代码：

def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
	if not beginWord or not endWord:
		return 0
	distance = {}
	for word in wordList:
		distance[word] = 0
	distance[beginWord] = 1
	return self.bfs(beginWord, endWord, distance, set())

def bfs(self, beginWord, endWord, dict, visited):
	queue = deque([beginWord])
	visited.add(beginWord)
	while queue:
		word = queue.popleft()
		if word == endWord:
			return dict[word]

		neighbors = self.get_next_words(word, dict)
		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 int ladderLength(String beginWord, String endWord, List<String> wordList) {
	// 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);
	
	Set<String> visited = new HashSet<>();
	Queue<String> q = new LinkedList<>();
	q.offer(beginWord);
	visited.add(beginWord);
	while(!q.isEmpty()) {
		String word = q.poll();
		if(endWord.equals(word))
			return dict.get(word);
		
		List<String> nextWords = getNextWords(word, dict);
		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²)</code>，空间复杂度O(n)，n为单词数。

---

算法II解题思路：

利用双向BFS，参考双向BFS概念
如果搜索不够广的话(例如类似于一条直线)，BFS会较慢，用双向BFS可解决此问题。双向BFS就是同时从起点和终点两个方向开始搜索，结果分存在map中，如果节点在另一个map中，
就意味着找到了一条连接起点和终点的最短路径。若任一queue为空，表明不会存在路径。如下图，前向BFS找到了结果。
搜索方式分为同步搜索和队列容量较少的先搜。本法采取前者

解题步骤：

1. 与单向BFS类似，但由于现在是双向，所以将BFS的通用部分提取出来，变量为queue, visited, distance, target_distance, target_distance是查找本方向
   的节点是否在对方搜索过的路径上代替endWord，距离为本方向的路径+对方的路径。while循环移到调用函数中。
2. while循环用两个queue不为空
3. 为了优化get_next_words重复调用，将结果存在graph中形成邻接表。这样的话，distance不用初始化为0，还可以用于记录重复节点代替visited。
4. 其他初始化步骤给endWord的BFS复制一次。

注意事项：

1. graph = collections.defaultdict(list)避免NPE，dict都尽量用此法

Python代码：

def ladderLength2(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
	if not beginWord or not endWord:
		return 0
	wordList.append(beginWord)
	graph, word_dict = collections.defaultdict(list), set(wordList)
	for word in wordList:
		graph[word] = self.get_next_words(word, word_dict)
	forward_distance, backward_distance = collections.defaultdict(int), collections.defaultdict(int)
	forward_distance[beginWord], backward_distance[endWord] = 1, 0

	forward_queue, backward_queue = deque([beginWord]), deque([endWord])
	forward_visited, backward_visited = set([beginWord]), set([endWord])
	while forward_queue and backward_queue:
		total_dis = self.bfs_from_start_or_end(graph, forward_queue, forward_distance, backward_distance)
		if total_dis > 0:
			return total_dis
		total_dis = self.bfs_from_start_or_end(graph, backward_queue, backward_distance, forward_distance)
		if total_dis > 0:
			return total_dis
	return 0

def bfs_from_start_or_end(self, graph, queue, distance, target_dict):
	word = queue.popleft()
	if word in target_dict and target_dict[word] > 0:  # the forward distance has all words initially
		return distance[word] + target_dict[word]

	neighbors = graph[word]
	for neighbor in neighbors:
		#if neighbor in visited:
		if neighbor in distance:
			continue
		queue.append(neighbor)
		# visited.add(neighbor)
		distance[neighbor] = distance[word] + 1
	return 0