LeetCode题解(0936):序列能否由指定印章印成(Python)
发布日期:2021-06-29 19:58:17
浏览次数:3
分类:技术文章
本文共 3409 字,大约阅读时间需要 11 分钟。
题目:(困难)
标签:字符串、正则表达式、贪心算法
解法 | 时间复杂度 | 空间复杂度 | 执行用时 |
---|---|---|---|
Ans 1 (Python) | – | – | 1796ms (13.89%) |
Ans 2 (Python) | O ( N ( N − M ) ) O(N(N-M)) O(N(N−M)) | O ( N ( N − M ) ) O(N(N-M)) O(N(N−M)) | 220ms (66.11%) |
Ans 3 (Python) | O ( N 2 × M ) O(N^2×M) O(N2×M) | O ( N ) O(N) O(N) | 100ms (94.44%) |
解法一(朴素的正则表达式):
class Solution: def movesToStamp(self, stamp: str, target: str) -> List[int]: # 生成正则表达式 S = len(stamp) if S == 1: regex = stamp repl = "#" else: regex = [] for i in range(0, S): tmp = [] for j in range(0, S): if j != i: tmp.append("[#" + stamp[j] + "]") else: tmp.append(stamp[j]) regex.append("".join(tmp)) regex = "|".join(regex) repl = "#" * S # 计算印制顺序 ans = [] while True: match = re.search(regex, target) if match: i1 = match.span()[0] i2 = match.span()[1] target = target[:i1] + repl + target[i2:] ans.append(i1) else: break # 判断印制是否成功 if target.count("#") == len(target): return list(reversed(ans)) else: return []
解法二(逆推法):
class Solution: def movesToStamp(self, stamp: str, target: str) -> List[int]: M, N = len(stamp), len(target) queue = collections.deque() # 当前新变化的坐标 done = [False] * N # 完成情况 ans = [] # 生成完成列表 A = [] for i in range(N - M + 1): made, todo = set(), set() for j, sch in enumerate(stamp): tch = target[i + j] if tch == sch: made.add(i + j) else: todo.add(i + j) A.append((made, todo)) if not todo: ans.append(i) for j in range(i, i + len(stamp)): if not done[j]: queue.append(j) done[j] = True while queue: i = queue.popleft() for j in range(max(0, i - M - 1), min(N - M, i) + 1): if i in A[j][1]: A[j][1].discard(i) if not A[j][1]: ans.append(j) for m in A[j][0]: if not done[m]: queue.append(m) done[m] = True if all(done): return ans[::-1] else: return []
解法三(逆推法):
class Solution: def movesToStamp(self, stamp: str, target: str) -> List[int]: M, N = len(stamp), len(target) NN, MM = "#" * N, "#" * M # 判断字符串是否符合目标 def match(s): for m in range(M): ch = s[m] if ch != "#" and ch != stamp[m]: return False return True ans = [] # 逆推法匹配结果 while target != NN: find = False for i in range(N - M + 1): tmp = target[i:i + M] if tmp == MM: continue if match(tmp): find = True ans.append(i) target = target[:i] + MM + target[i + M:] if not find: return [] return list(reversed(ans))
转载地址:https://dataartist.blog.csdn.net/article/details/108085799 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
能坚持,总会有不一样的收获!
[***.219.124.196]2024年05月01日 18时36分43秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
laravel之中间件三步走--star.hou
2019-04-30
PHP Windows环境安装Solr扩展
2019-04-30
Paypal Express Checkout快速结账API心得--Star.Hou
2019-04-30
支付网关设计感悟(一)Star.Hou
2019-04-30
支付网关设计感悟(二)Star.Hou
2019-04-30
laravel文件上传excel - star.Hou
2019-04-30
Mysql复制数据库--star.Hou
2019-04-30
Js关于光标对象与定位插入图片
2019-04-30
redis队列处理在PHP里的使用 star.Hou的红楼一梦
2019-04-30
elasticsearch搜索之范围维度 Star.hou原创
2019-04-30
facebook市场营销SDK之个人理解 Star.hou原创
2019-04-30
Redis AOF之重写 Star.hou原创
2019-04-30
Redis之主从配置的心跳 Star.hou原创
2019-04-30
vim or sed字符串批量替换
2019-04-30
redis之队列处理回滚记录 star.Hou
2019-04-30
Laravel repository数据仓库使用 Star.hou红楼一梦
2019-04-30
Laravel之文件上传
2019-04-30
Redis 3.2.3 源码安装(centos6.8)
2019-04-30