[python leetcode] Word Ladder II (very hard)[非常难,放弃]
Word Ladder II描述
Given two words (start and end), and a dictionary, find all shortest transformation sequence(s) from start
to end, such that:
· Only one letter can be changed at a time
· Each intermediate word must exist in the dictionary
For example, Given:
start = "hit"
end = "cog"
dict = ["hot","dot","dog","lot","log"]
Return
[
["hit","hot","dot","dog","cog"],
["hit","hot","lot","log","cog"]
]
Note:
· All words have the same length.
· All words contain only lowercase alphabetic characters.
题意：给定start单词，end单词，以及一个dict字典。要求找出start到end的所有最短路径，路径上的每个单词都要出现在dict中，且每次改变一个字母。如start="hit"; end="cog"; dict={"hot","dot","dog","lot","log"}，则答案为：[["hit","hot","dot","dog","cog"],["hit","hot","lot","log","cog"]]。这是leetcode oj给的例子。我在实现的时候发现这个例子有点问题：end单词不在dict中。实际的测试用例应该是start和end单词都在dict中的，因为如果提前做一个删除start或者end单词的操作的话，就通不过了。我用正确的程序去测试oj给的这个例子也无法通过，就姑且认为start单词和end单词都在dict中吧，这样写出来的程序才能通过。Word Ladder II这一道题还是比较难的，是leetcode oj中通过率最低的一道题。而由于我一直在用python来刷题，且一直在网上找不到用python写的解法，自己又写不出来，所以参考了网上的C++解法以及kitt的python程序，在此表示感谢。
解题关键点：
1，这里的dict是python中的set()类型。
2，使用前驱单词表prevMap(是字典类型)来记录单词的前驱。比如prevMap={cog:}表示cog的前驱是：log和dog。
3，在word ladder这道题中我们使用了队列，在word ladder ii中也需要使用队列，只不过在这个程序中使用了两个set()来模拟队列(candidates)。candidates中存储的是前一层的单词。如{dot，lot}为第3层单词。在程序开始执行时，先将candidates中的单词（前一层的单词）在dict中删除，再将candidates清空，然后根据candidates中的单词寻找下一层的单词，如{dot，lot}的下一层为{dog，log}，并将{dog，log}存入candidates中，同时将单词存入前驱单词表中。下一次循环开始时，上一次循环的candidates变成了candidates，而上一次循环的candidates变成了candidates并清空。如此反复执行，当某一次循环中的candidates中出现了end单词时，说明我们的路径已经找出来了，工作完成了。
4，程序中使用了一个子函数buildpath来重建每一条路径。如oj给的例子所产生的prevMap={‘cog’:[‘log’,’dog’], ‘log’:[‘lot’], ‘dog’:[‘dot’], ‘lot’:[‘hot’],’dot’:[‘hot’], ‘hot’:[‘hit’]}，这个prevMap可以使用DFS来重建每一条路径。
本解法来自:
http://www.cnblogs.com/zuoyuan/p/3697045.html
但是很多细节不明白,寻求大家的帮助.
1 class Solution:
2 # @param start, a string
3 # @param end, a string
4 # @param dict, a set of string
5 # @return a list of lists of string
6 def findLadders(self, start, end, dict):
7 def buildpath(path, word): # path is a list; word is a string
8 if len(prevMap)==0: #prevMap: dict#Blank prevMap means all the node in the path is visited
9 path.append(word);
10 currPath=path[:] # hard copy path to currPath. No link between pat and currPath
11 currPath.reverse();
12 result.append(currPath)
13 path.pop(); #remove the end element
14 return
15 path.append(word)
16 for iter in prevMap: # reverse the path,
17 buildpath(path, iter)
18 path.pop()
19
20 result=[]
21 prevMap={} # prevMap is a dict
22 length=len(start)
23 for i in dict: #dict: is a set
24 prevMap=[] # set the value for each key as blank string
25 candidates=; current=0; previous=1
26 candidates.add(start) # set0 add start
27 while True:
28 current, previous=previous, current #下一次循环开始时，上一次循环的candidates变成了candidates，而上一次循环的candidates变成了candidates并清空
29 for i in candidates: dict.remove(i) #先将candidates中的单词（前一层的单词）在dict中删除
30 candidates.clear() #再将candidates清空
31 for word in candidates: #再据candidates中的单词寻找下一层的单词
32 for i in range(length):
33 part1=word[:i]; part2=word
34 for j in 'abcdefghijklmnopqrstuvwxyz':
35 if word!=j:
36 nextword=part1+j+part2
37 if nextword in dict:
38 candidates.add(nextword) #将下一层存入candidates中
39 prevMap.append(word) #同时将单词存入前驱单词表中
40 if len(candidates)==0: return result #当集合为空,返回结果
41 if end in candidates: break #当循环中的candidates中出现了end单词时，说明我们的路径已经找出来了，工作完成了。
42 buildpath([], end) #重建每一条路径。prevMap is a dict，这个prevMap可以使用DFS来重建每一条路径。
43 return result
页:
[1]