【Leetcode】820. Short Encoding of Words
admin
2024-03-18 06:40:48

题目地址：

https://leetcode.com/problems/short-encoding-of-words/description/

给定一个英文小写字母的单词列表AAA，要求构造一个最短的字符串sss作为该列表的一种编码，编码方式为：
1、sss以'#'结尾；
2、解码结果搭配一个非负整数数组BBB，BBB与AAA长度相等，并且从s[B[i]]s[B[i]]s[B[i]]开始向后直到最近的'#'之间的子串即为A[i]A[i]A[i]。
求sss的长度。

可以用Trie。如果某两个个串，其中一个是另一个的后缀，显然可以用那个最长的来避免编码的重复。我们在AAA上定义一个偏序关系，如果aaa是bbb的后缀，则a'#'结尾）之总和。可以将AAA中所有字符串ttt翻转一下然后加入Trie中，将沿途的所有节点做标记（除了插入完成之后所到达的节点），然后再求所有未标记的节点所对应的字符串的长度（加111）的总和即可。代码如下：

class Solution {public:struct Node {Node* ne[26];bool valid;Node() : valid(true) { fill(ne, ne + 26, nullptr); }};Node* root;void insert(string& s, unordered_map& mp) {auto* p = root;for (char ch : s) {p->valid = false;int idx = ch - 'a';if (!p->ne[idx]) p->ne[idx] = new Node();p = p->ne[idx];}mp[p] = s.size();}int minimumLengthEncoding(vector& words) {root = new Node();unordered_map mp;for (int i = 0; i < words.size(); i++) {auto& s = words[i];reverse(s.begin(), s.end());insert(s, mp);}int res = 0;for (auto& [p, len] : mp)if (p->valid) res += len + 1;return res;}
};

时空复杂度O(∑lAi)O(\sum l_{A_i})O(∑lAi​​)。

词库加载错误:未能找到文件“E:\highferrum_mysql\Configuration\Dict_Stopwords.txt”。

上一篇：玩家必看攻略新九方大厅有透视挂吗!其实有挂-知乎

下一篇：科技分享、逍遥湖北麻将有透视挂吗,原来真的有挂-知乎

相关内容

热门资讯

AI“幻觉”的克星来了！海致科... 21世纪经济报道记者 赵云帆 报道作为AI行业的“卖水人”，芯片半导体，数据中心与云计算等行业企业受...
V观财报｜新开源董事赵威因其子... 　　中新经纬6月23日电 博爱新开源医疗科技集团股份有限公司(下称“新开源”)23日发布公告称，公司...
“巨头”这顶帽子，安踏撑得起来... 最近，高盛首次提出了一个新概念——“中国民营十巨头”，引起很大争议。它把腾讯、阿里、小米、比亚迪、美...
天猫618创下近三年最快增速：... 文 / 四海来源 / 节点财经过去提到大促，很多人的印象是价格内卷和玩法复杂，但这个618，情况已经...
王思聪撤退、何猷君接盘！“国内... “赌王之子”接棒“国民老公”的寰聚商业。作者 | 伍玥编辑丨高岩来源 | 野马财经继电竞行业之后，两...
当养老遇上FOF：一场关于未来... 作者 | 傅斯特曾几何时，养老对于许多年轻人来说，还是一个很遥远的话题。但近年来，随着"延迟退休"政...
拼多多打通 “新荔枝道”，此去... 作者 | 逍道一荔枝熟了，恰逢丰年，大江南北都能品尝到来自岭南的这一口甜蜜。随着《长安的荔枝》热播，...
英联股份：公司复合集流体板块的... 6月23日晚间，广东英联包装股份有限公司（英联股份，002846.SZ）发布股票交易异常波动公告，公...
【会员风采】青拓特钢中厚板项目... 2025年6月22日9时28分，青拓集团董事长姜海洪、集团副总裁兼青拓特钢公司董事长项炳庆、副总裁周...
青海春天危局：听花酒滞销，航空... 文｜九州商业观察 在资本市场与白酒市场的风云变幻中，*ST春天正站在命运的十字路口，努力寻找着突围...
美团调整部分城市社区团购业务，... 6月23日，有消息称，从6月23日起，美团优选在北京、四川、重庆、湖南、湖北、陕西、上海、福建等地的...
保姆级教程！个人炒贵金属开户流... 2025年越来越多的个人投资者开始关注贵金属投资，但面对复杂的交易规则和选择平台的风险，却让许多新手...
价格涨幅超黄金！铂金、白银异军... 这两年，黄金总是重复以两种方式登上热搜：大涨与大跌。 进入6月，黄金登上热搜的趋向更加明显——大跌。...
丁玉梅，硬核包租婆来了 丁玉梅... 作者| 猫哥来源| 大猫财经Pro&是史大郎消失许久的许家印前妻丁玉梅，终于又传来消息，她通过5家离...
徐冰卸任，商汤再度“甩包袱” 近期，徐冰卸任相关职务，这一变动引发关注。而商汤在此之际再度选择“甩包袱”，似乎在其发展历程中又迈出...
2.27亿资金抢筹金龙羽，机构... 6月23日，上证指数上涨0.65%，深证成指上涨0.43%，创业板指上涨0.39%。盘后龙虎榜数据显...
6月最火赛道！稳定币板块暴拉8... 本文来源：时代周报 作者：王苗苗 图源：图虫创意稳定币概念股引爆六月行情。6月23日，A股稳定币概...
KKR拟收购一家中国饮料公司8... 作者 | 钟艺璇编辑 | 乔芊 杨轩36氪独家获悉，美国私募股权机构KKR拟收购一家中国饮料公司85...
托底力量显现，关注几个行业蓄力
兴业证券：选举苏军良为董事长 ... 6月23日，兴业证券股份有限公司（兴业证券，601377.SH）公告称，公司第六届董事会第三十二次会...
新品发布，AMD能否挑战英伟达... 文 / 零度来源 / 节点财经就在一周之前，超威半导体公司（AMD）首席执行官苏姿丰放出豪言称，AM...
深圳、东莞，联手干了件大事！ ... 原创 刘博团队上周末，两条关于深圳光明的新闻刷屏了。6月21日，在深圳科学技术馆，由深莞两地市长、顶...
原创 小... 6月23日，小鹏汇天宣布一项人事任命：杜超加入小鹏汇天，出任首席财务官（CFO）兼副总裁。结合此前小...
华为发布盘古大模型5.5，技术... “一年以来，盘古大模型深入行业解难题，在30多个行业、500多个场景中落地。”在华为开发者大会202...
熊园：下半年政策有4大节点 熊... 熊园朱慧（熊园 系国盛证券首席经济学家、中国首席经济学家论坛理事）近半月，中美经贸磋商机制首次会议在...
高瑞东：如何解读5月份财政数据... 高瑞东 王佳雯（高瑞东系光大证券首席经济学家、中国首席经济学家论坛理事）核心观点事件：2025年1-...
寻找“异类”：黄明明揭秘投中李... Agent创业时代，黄明明把赌注押在“人”身上。采访｜《中国企业家》记者 孔月昕 闫俊文文｜《中国企...
“红包雨”来袭，本周超300只... A股市场迎来一波“红包雨”，就在本周，超三百家上市公司的年报分红到账。Wind统计显示，6月23日至...
「定焦One」作品入选中国记协... 定焦One（dingjiaoone）原创6月23日，中国记协公布“我的代表作”栏目第六十三期作品。「...
浪潮信息：拟2亿元-3亿元回购... 6月23日，浪潮电子信息产业股份有限公司（浪潮信息，000977.SZ）公告，公司拟使用自有资金和自...