kazi1@的部落格

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 intermediate word must exist in the word list

For example,

Given:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]

As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.

Note:

• Return 0 if there is no such transformation sequence.
• All words have the same length.
• All words contain only lowercase alphabetic characters.

class Solution(object):
    def ladderLength(self, beginWord, endWord, wordList):
        """
        :type beginWord: str
        :type endWord: str
        :type wordList: Set[str]
        :rtype: int
        """
        hmap = {}
        for w in wordList:
            hmap[w] = 0
        if beginWord in hmap:
            del hmap[beginWord]
        hmap[endWord] = 0
        
        que = [[beginWord, 1]]
        while len(que) > 0:
            n = que.pop(0)
            nw = list(n[0])
            nd = n[1]
            if n[0] == endWord:
                return nd

            if len(hmap) > 0:
                for x in xrange(len(nw)):
                    y = nw[x]
                    for c in xrange(ord('a'),ord('z')+1):
                        if y != chr(c):
                            nw[x] = chr(c)
                            ww = ''.join(nw)
                            if ww in hmap:
                                que.append([ww, nd+1])
                                del hmap[ww]
                    nw[x] = y
        return 0  

class Solution:
    # @param start, a string
    # @param end, a string
    # @param dict, a set of string!!!dict is a set type!!!
    # @return an integer
    def ladderLength(self, start, end, dict):
        dict.add(end)
        q = []
        q.append((start, 1))
        while q:
            curr = q.pop(0)
            currword = curr[0]; currlen = curr[1]
            if currword == end: return currlen
            for i in range(len(start)):
                part1 = currword[:i]; part2 = currword[i+1:]
                for j in 'abcdefghijklmnopqrstuvwxyz':
                    if currword[i] != j:
                        nextword = part1 + j + part2
                        if nextword in dict:
                            q.append((nextword, currlen+1)); 
                            dict.remove(nextword)
        return 0