Surrounded Regions @ LeetCode (Python)
Remove Element @ LeetCode (Python)

Word Ladder @ LeetCode (Python)

kitt posted @ 2014年2月23日 18:38 in LeetCode , 9841 阅读

使用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

 

 

Avatar_small
yzl232 说:
2014年3月06日 11:33

你这个解法不错。 很短啊。
你做过word ladder ii 吗?

Avatar_small
kitt 说:
2014年3月06日 19:30

word ladder ii我总超时, 过了的话我就把代码贴上来~@yzl232:

Avatar_small
yzl232 说:
2014年3月19日 01:13

蛮经常看你的博客了。 是不是150道题目刷了100多道了? leetcode我有100道了。
你是不是也是下半年就要硕士毕业?
你的网站没有私信功能, 不然我想加linkedin或者Facebook了

Avatar_small
kitt 说:
2014年3月19日 12:26

@yzl232:
对的,5月份毕业, 我的邮箱是chaoren.hust@gmail.com

Avatar_small
xyz 说:
2014年4月26日 13:17

为啥要用deque啊?这里看起来list完全够了,append是一样的,popleft就pop([0])不就可以了么?

Avatar_small
xyz 说:
2014年4月26日 13:31

另外双向怎么做?网上找到bi-directional那个代码风格太飘忽我看不懂啊,是不是同样建一个queueRight然后每次queue里pop一个currword出来看在不在queueRight里面?但是queue的搜索时间是O(n)啊

Avatar_small
kitt 说:
2014年4月26日 14:37

@xyz: 双向我也不太懂。用deque不用list是因为效率的问题,http://stackoverflow.com/questions/1296511/efficiency-of-using-a-python-list-as-a-queue

Avatar_small
Jing 说:
2014年9月18日 13:09
我和楼主一样的思路但因为用
 
for j in range(ord('a'), ord('z')+1):
                    newWord = cur[:i]+chr(j)+cur[i+1:]
而不是
for j in 'abcdefghijklmnopqrstuvwxyz'
所以超时了。改过之后就通过了。。。
 
P.S. 楼主是HUST的么?加linkedin或者facebook吧~
Avatar_small
liuchang 说:
2016年10月09日 20:06

请问为什么会在最后return 0 呢

Avatar_small
kowalski 说:
2017年8月24日 03:43

word ladder 2在Leetcode已经 TLE了,lintcode可以通过

Avatar_small
kowalski 说:
2017年8月24日 03:44

@liuchang: 题目要求如果不存在合理的sequence,就返回0

Avatar_small
diyin 说:
2017年12月22日 03:13

是的鬼地方飞得更高

Avatar_small
AP 10th Civics Model 说:
2022年9月17日 13:10

Department of Education and Secondary Education Board has designed the AP SSC Civics Model Paper 2023 Pdf with answers for Telugu Medium, English Medium & Urdu Medium Students of the State Board. Every year there are a huge number of teaching staff and educational portals of the state have suggested the practice question bank with revision questions for both medium students of the board. AP 10th Civics Model Paper In civics, students learn to contribute to public processes and discussions of real issues. Students can also learn civic practices such as voting, volunteering, jury service, and joining with others to improve society. Civics enables students not only to study how others participate but also to practice participating and taking informed action themselves.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter