LeetCode 527. 单词缩写(Trie树)
发布日期:2021-07-01 03:31:29
浏览次数:3
分类:技术文章
本文共 2401 字,大约阅读时间需要 8 分钟。
文章目录
1. 题目
给定一个由n个不重复非空字符串组成的数组,你需要按照以下规则为每个单词生成最小的缩写。
- 初始缩写由起始字母+省略字母的数量+结尾字母组成。
- 若存在冲突,亦即多于一个单词有同样的缩写,则使用更长的前缀代替首字母,直到从单词到缩写的映射唯一。换而言之,最终的缩写必须只能映射到一个单词。
- 若缩写并不比原单词更短,则保留原样。
示例:输入: ["like", "god", "internal", "me", "internet", "interval", "intension", "face", "intrusion"]输出: ["l2e","god","internal","me","i6t","interval","inte4n","f2e","intr4n"] 注意:n和每个单词的长度均不超过 400。每个单词的长度大于 1。单词只由英文小写字母组成。返回的答案需要和原数组保持同一顺序。
来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/word-abbreviation
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
2. 解题
- 对字符串进行分组(首尾字符+长度),这种情况,缩写才可能一样
- 组内单词插入trie树,记录每个节点的占用次数,如果只出现1个人占用的,即可以确定唯一的缩写
class trie{ public: trie* next[26] = { NULL}; int freq = 0; void insert(string& s) { trie* cur = this; for(int i = 0; i < s.size(); i++) { if(!cur->next[s[i]-'a']) cur->next[s[i]-'a'] = new trie(); cur = cur->next[s[i]-'a']; cur->freq++; } }};class Solution { public: vectorwordsAbbreviation(vector & dict) { unordered_map > group; unordered_map w_id; for(int i = 0; i < dict.size(); ++i) { string g = dict[i][0]+to_string(dict[i].size())+dict[i].back(); group[g].push_back(dict[i]); //按首尾字符+长度信息给字符串分组 w_id[dict[i]] = i;//序号信息 } vector ans(dict.size()); for(auto& strs : group)//分组 { trie* t = new trie(), *cur = t; for(auto& s : strs.second) t->insert(s);//组内单词插入trie树 for(auto& s : strs.second)//遍历组内的单词 { cur = t; string temp;//缩写 for(int i = 0; i < s.size(); i++)//在trie中查找 { if(cur->next[s[i]-'a']->freq == 1)//自己独有的字符 { int count = s.size()-i-2; if(count >= 2)//缩写字符超过1个 temp = s.substr(0,i+1)+to_string(count)+s.back(); else temp = s; break; } cur = cur->next[s[i]-'a']; } ans[w_id[s]] = temp; } } return ans; }};
332 ms 330.2 MB
我的CSDN
长按或扫码关注我的公众号(Michael阿明),一起加油、一起学习进步!
转载地址:https://michael.blog.csdn.net/article/details/107951276 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
不错!
[***.144.177.141]2024年04月17日 06时53分23秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
2 QCreator调试并查看源码
2019-05-02
4 Qt 之 pro 配置多个子工程/子模块
2019-05-02
12 Qt 之 QToolBox、QLCDNumber
2019-05-02
32 Qt 之绘图之绘制一个漂亮的西瓜
2019-05-02
35 Qt 之绘制闪烁文本
2019-05-02
QT知识点总结(一)
2019-05-02
Unix环境变量--文件操作
2019-05-02
Unix环境变量--进程管理
2019-05-02
Unix环境变量--线程基础
2019-05-02
tinyhttpd源码学习1
2019-05-02
Plus One
2019-05-02
Reverse Linked List II
2019-05-02
涨姿势:为啥MySQL官方不推荐使用uuid或者雪花id作为主键?
2019-05-02
一个小小的签到功能,到底用MySQL还是Redis?
2019-05-02
36岁退休!阿里 P8 六年实现“财务自由”,裸辞环游世界!
2019-05-02
高赞回答:为什么高级程序员不必担心自己的技术过时?
2019-05-02
SpringBoot集成WebSocket,实现后台向前端推送信息
2019-05-02
Windows 10将预装Windows Terminal
2019-05-02
字符编码,原来是SQL不走索引的元凶之一!
2021-07-05
老板要我开发一个简单的工作流引擎 !
2021-07-05