当前位置: 首页 > news >正文

赣州培训学做网站深圳网站推广公司

赣州培训学做网站,深圳网站推广公司,国外做游戏的视频网站有哪些,网址域名查询官网Leetcode 3213. Construct String with Minimum Cost 1. 解题思路2. 代码实现 题目链接:3213. Construct String with Minimum Cost 1. 解题思路 这一题的话思路上还是比较直接的,就是一个trie树加一个动态规划,通过trie树来快速寻找每一个…
  • Leetcode 3213. Construct String with Minimum Cost
    • 1. 解题思路
    • 2. 代码实现
  • 题目链接:3213. Construct String with Minimum Cost

1. 解题思路

这一题的话思路上还是比较直接的,就是一个trie树加一个动态规划,通过trie树来快速寻找每一个位置作为起点时能够匹配的全部字符串,然后用一个动态规划来获取最优剪切方案。

其中,关于trie树的内容可以参考我之前的博客《经典算法:Trie树结构简介》,这里就不过多展开了。

然后当前的实现其实还蛮暴力的,时间上勉勉强强通过了全部测试样例,不过应该可以通过剪枝以及优化trie树内的内容来进行一下优化,有兴趣的读者可以考虑一下其具体实现,这里就不过多进行展开了。

2. 代码实现

给出python代码实现如下:

class Trie:def __init__(self):self.trie = {}def add_word(self, word, cost):trie = self.triefor c in word:trie = trie.setdefault(c, {})if "eos" not in trie:trie["eos"] = (word, cost)elif cost < trie["eos"][1]:trie["eos"] = (word, cost)returndef find_all_prefix(self, word):prefixs = []trie = self.triefor c in word:if c not in trie:breaktrie = trie[c]if "eos" in trie:prefixs.append(trie["eos"])return prefixsclass Solution:def minimumCost(self, target: str, words: List[str], costs: List[int]) -> int:trie = Trie()for word, cost in zip(words, costs):trie.add_word(word, cost)n = len(target)ans = math.inf@lru_cache(None)def dp(idx):nonlocal ansif idx >= n:return 0prefixs = trie.find_all_prefix(target[idx:])if prefixs == []:return math.infreturn min(c + dp(idx+len(w)) for w, c in prefixs)ans = dp(0)return ans if ans != math.inf else -1

提交代码评测得到:耗时10897ms,占用内存267.2MB。

http://www.fp688.cn/news/146209.html

相关文章:

  • 杭州网站艰涩安徽网络关键词优化
  • 做装修的网站怎么做好厦门人才网招聘
  • 网站关键词怎么选河北网站seo
  • 网站建设专家最新引流推广方法
  • 网站编辑电子商务网站运营专员抖音代运营
  • 如何做一网站首页怎样免费给自己的公司做网站
  • 哪个网站做x展架比较好 知乎黑帽seo培训大神
  • 信息作业网站下载自助网站建设
  • 甘肃省住房和城乡建设局网站首页免费建站网站
  • 常州做网站要多少钱seo推广要多少钱
  • 延安网站建设电话百度云资源搜索网站
  • 邢台网站建设哪家好精准营销理论
  • 百度怎样建立一个网站百度下载app安装
  • 棋牌搭建工具前端优化网站
  • 注册网站会有哪些风险新东方雅思培训机构官网
  • 聊城网站建设报价电商如何推广自己的产品
  • 怎样做自己的手机网站淘宝搜索排名
  • 织梦怎么做单页网站在线刷高质量外链
  • b站有没有官方推广的价格晋城seo
  • php与 wordpressseo服务公司上海
  • 精品建站长春网站公司哪家好
  • php部署网站厦门seo收费
  • 微信对接网站可以做301跳转吗广告联盟看广告赚钱
  • 金华住房和城乡建设部网站百度首页网站推广多少钱一年
  • 鞍山公司做网站网络营销的概念和特征
  • 网络营销推广技术分析深圳关键词优化怎么样
  • 青岛网站建设培训seo工具是什么意思
  • 上海优化公司英文网站seo发展前景
  • 大连 找人做网站正规营销培训
  • 政府网站集约化建设通知免费seo技术教程