📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
查看: 4150| 回复: 3
跳转到指定楼层
上一主题 下一主题
收起左侧

[学Python/Perl] [Leetcode]听说Word Ladder II是最难的题

全局:

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x
Python 20行可以过
  1. class Solution:
  2.     def findLadders(self, start, end, words):
  3.         lowercase = map(chr, range(97, 123))
  4.         words.add(end)
  5.         words.add(start)
  6.         next_word = {}
  7.         for w in words:
  8.             next_word[w] = [w[:i]+c+w[i+1:] for i in xrange(len(w)) for c in lowercase if c!=w[i] and w[:i]+c+w[i+1:] in words]
  9.         queue, dist = collections.deque(), {}
  10.         dist[start] = 1
  11.         queue.append(start)
  12.         while queue:
  13.             head = queue.popleft()
  14.             for w in next_word[head]:
  15.                 if w not in dist:
  16.                     dist[w] = dist[head]+1
  17.                     queue.append(w)
  18.         def dfs(i):
  19.             return [[end]] if i==end else [[i]+path for j in next_word[i] if dist[j]==dist[i]+1 for path in dfs(j)]
  20.         return dfs(start)
复制代码

上一篇:Career ride里的一个OS的题目,关于deadlock的
下一篇:Lintcode新题 Inorder Successor in BST 怎么做?
推荐
ZionHill 2015-10-6 02:39:38 | 只看该作者
全局:
壮哉我大推土机Python
Python大法好,退C艹保平安
回复

使用道具 举报

🔗
readman 2015-10-6 02:49:24 | 只看该作者
全局:
- - 现在lc里有几个人一直在玩golf
回复

使用道具 举报

🔗
 楼主| Linzertorte 2015-10-6 03:18:55 | 只看该作者
全局:
另外Expression Add Operators也推倒了。没有用eval作弊。。
  1. class Solution(object):
  2.     def addOperators(self, num, target):
  3.         n = len(num)
  4.         def factor(s):
  5.             if len(s)==0: return ['']
  6.             n = 1 if s[0]=='0' else len(s)
  7.             r = []
  8.             for i in xrange(0,n):
  9.                 op = '' if i+1 ==len(s) else '*'
  10.                 r += [s[:i+1]+op+p for p in factor(s[i+1:])]
  11.             return r
  12.         def evaluate(s):
  13.             s = s.split('*')
  14.             return reduce(lambda y,x: int(x)*y, s, 1)
  15.         dp = {}
  16.         def dfs(i,target):
  17.             if i==-1:
  18.                 return [''] if target==0 else []
  19.             if (i,target) in dp: return dp[i,target]
  20.             r = []
  21.             for j in xrange(i,-1,-1):
  22.                 for f in factor(num[j:i+1]):
  23.                     x = evaluate(f)
  24.                     if j == 0:
  25.                         r+=[f] if x==target else []
  26.                     else:
  27.                         r += [ p+"+"+f for p in dfs(j-1,target-x)]
  28.                         r += [ p+'-'+f for p in dfs(j-1,target+x)]
  29.             dp[i,target] = r
  30.             return r
  31.         return dfs(n-1,target)
复制代码
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

>
快速回复 返回顶部 返回列表