LeetCode 127 Word Ladder

LeetCode 127 Word Ladder

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:

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.

Example 2:

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

Output: 0

*Explanation:

The endWord “cog” is not in wordList, therefore no possibletransformation.

题目大意：

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

解题思路：

这题是最短路径题，第一时间想到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=O(L2)产生新字符串需要L
时间复杂度为O(n*L2)，空间复杂度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