使用BFS, 单词和length一块记录, dict中每个单词只能用一次, 所以用过即删。dict给的是set类型, 检查一个单词在不在其中(word in dict)为O(1)时间。设单词长度为L, dict里有N个单词, 每次扫一遍dict判断每个单词是否与当前单词只差一个字母的时间复杂度是O(N*L), 而每次变换当前单词的一个字母, 看变换出的词是否在dict中的时间复杂度是O(26*L), 所以要选择后者。Python真是慢啊, 同样的代码C++ 668ms过, Python 1416ms过。看到双向BFS的做法, 应该能更快, 再研究研究。

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):
        dict.add(end)
        wordLen = len(start)
        queue = collections.deque([(start, 1)])
        while queue:
            curr = queue.popleft()
            currWord = curr[0]; currLen = curr[1]
            if currWord == end: return currLen
            for i in xrange(wordLen):
                part1 = currWord[:i]; part2 = currWord[i+1:]
                for j in 'abcdefghijklmnopqrstuvwxyz':
                    if currWord[i] != j:
                        nextWord = part1 + j + part2
                        if nextWord in dict:
                            queue.append((nextWord, currLen + 1))
                            dict.remove(nextWord)
        return 0

 

Word Ladder II自己写的一直超时，看了discuss里的这个解法，用defaultdict，很好很强大，佩服佩服！defaultdict和普通dict的不同就是它允许有默认值，比如d = collections.defaultdict(set), 即使没有5这个key，d[5]仍然有值，是set([])。如果用int来初始化，d[5]默认值就是0。用list来初始化，d[5]默认值就是[]。我根据自己的理解写了一下注释，再次赞Python的简洁。

# 2015-06-18  Runtime: 712 ms
class Solution:
    # @param start, a string
    # @param end, a string
    # @param dict, a set of string
    # @return a list of lists of string
    def findLadders(self, start, end, dic):
        # thanks to https://leetcode.com/discuss/24191/defaultdict-for-traceback-and-easy-writing-lines-python-code
        dic.add(end)
        level = set([start])
        # key is word, value is parent word, e.g. {'hot': set(['hit']), 'cog': set(['log', 'dog'])}
        # In each level, defaultdict(set) can remove duplicates, first we need to get parent dictionary
        parents = collections.defaultdict(set)
        while level and end not in parents:
            next_level = collections.defaultdict(set)
            for word in level:
                for char in 'abcdefghijklmnopqrstuvwxyz':
                    for i in xrange(len(start)):
                        childWord = word[:i] + char + word[i+1:]
                        if childWord in dic and childWord not in parents: next_level[childWord].add(word)
            level = next_level
            parents.update(next_level)
            
        # then according parent dictionary, build result from end word to start word
        res = [[end]]
        while res and res[0][0] != start:
            res = [[p] + r for r in res for p in parents[r[0]]]
        return res

 

 

[取消回复评论]

昵称 登录 E-mail: *
Web:
Twitter:

当有新评论通过 E-mail 通知我

(输入验证码)

or Ctrl+Enter