Word Ladder
Given two words (start and end), and a dictionary, find the length of shortest transformation sequence from start to end, such that:
Only one letter can be changed at a time
Each intermediate word must exist in the dictionary
Notice
Return 0 if there is no such transformation sequence.
All words have the same length.
All words contain only lowercase alphabetic characters.
Example
Given:
start = "hit"
end = "cog"
dict = ["hot","dot","dog","lot","log"]
As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.
Solution:
由于需要找到最短路径的长度,求最短路径可以直接想到BFS的遍历,同时又可以想到是否可以用动态规划,以后可以验证下。 这道题最难的地方就是,把单词跟单词的关系转化成,图中节点与节点的关系,一个单词只变动一个字母,可以得到词典中一个新的单词,那么这两个单词相邻,长度为1. 第二个难点是,如果直接拿单词跟词典里面的词比较是否就差一个字母不同,这样的时间复杂度是O(MN) 这里面比较巧的方法就是,可以直接单词从第一字母到最后一个字母不停的拿26个字母中的每个区匹配得到新的单词,然后判断是否存在,这样的时间复杂度是: O(M*26)
class Solution:
# @param start, a string
# @param end, a string
# @param dict, a set of string
# @return an integer
def ladderLength(self, start, end, dict):
# write your code here
dict.add(end)
q = collections.deque([(start, 1)])
while len(q) > 0:
curr = q.popleft()
currword = curr[0]; currlen = curr[1]
if currword == end:
return currlen
for i in range(len(currword)):
first = currword[:i]; second = currword[i + 1:]
for j in 'abcdefghijklmnopqrstuvwxyz':
newword = first + j + second
if currword[i] != j:
if newword in dict:
q.append((newword, currlen + 1))
dict.remove(newword)
return 0
Last updated
Was this helpful?