一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 988|回复: 3
收起左侧

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

[复制链接] |试试Instant~ |关注本帖
Linzertorte 发表于 2015-10-6 01:52:28 | 显示全部楼层 |阅读模式

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

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

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)
复制代码
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)
复制代码
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-3 03:16

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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