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?