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