[LeetCode] 527. Word Abbreviation 单词缩写
Given an array of n distinct non-empty strings, you need to generate minimal possible abbreviations for every word following rules below.
- Begin with the first character and then the number of characters abbreviated, which followed by the last character.
- If there are any conflict, that is more than one words share the same abbreviation, a longer prefix is used instead of only the first character until making the map from word to abbreviation become unique. In other words, a final abbreviation cannot map to more than one original words.
- If the abbreviation doesn't make the word shorter, then keep it as original.
Example:
Input: ["like", "god", "internal", "me", "internet", "interval", "intension", "face", "intrusion"]
Output: ["l2e","god","internal","me","i6t","interval","inte4n","f2e","intr4n"]
Note:
- Both n and the length of each word will not exceed 400.
- The length of each word is greater than 1.
- The words consist of lowercase English letters only.
- The return answers should be in the same order as the original array.
这道题让我们求单词的缩写形式,就是首尾字母加上中间字符的个数组成的新字符串,但是要求是不能有重复的缩写字符串,而且说明如果缩写字符串的长度并没有减小的话就保留原来的字符串,比如 god,缩写成 g1d 也没啥用,所以仍是 god。博主刚开始在研究题目中给的例子的时候有些疑惑,虽然知道 internal 和 interval 的缩写形式都是 i6l,会冲突,博主刚开始不明白的是,为什么不能一个是 i6l,一个是 in5l,这样不就不冲突了么,而题目中的缩写形式居然都是原字符串。后来才搞清楚题目原来是说只要有冲突的都不能用,而 internal 和 interval 是典型的死杠上的一对,i6l,in5l,int4l,inte3l,inter2l,统统冲突,而再往后的缩写长度就和原字符串一样了,所以二者就都保留了原样。理解了题意就好办了,由于每个单词的缩写形式中数字前面的字母个数不一定相同,所以用一个 pre 数组来记录每个单词缩写形式开头字母的长度,初始化都为1,然后先求出所有单词 pre 为1的缩写形式,再来进行冲突处理。遍历每一个缩写字符串,进行 while 循环,新建一个 HashSet,然后遍历其他所有字符串,所有发现冲突字符串,就把冲突字符串的坐标存入 HashSet 中,如果没有冲突,那么 HashSet 为空,直接 break 掉,如果有冲突,那么还要把当前遍历的位置i加入 HashSet 中,然后遍历 HashSet 中所有的位置,对其调用缩写函数,此时 pre 对应的值自增1,直到没有冲突存在为止,参见代码如下:
class Solution {
public:
vector<string> wordsAbbreviation(vector<string>& dict) {
int n = dict.size();
vector<string> res(n);
vector<int> pre(n, );
for (int i = ; i < n; ++i) {
res[i] = abbreviate(dict[i], pre[i]);
}
for (int i = ; i < n; ++i) {
while (true) {
unordered_set<int> st;
for (int j = i + ; j < n; ++j) {
if (res[j] == res[i]) st.insert(j);
}
if (st.empty()) break;
st.insert(i);
for (auto a : st) {
res[a] = abbreviate(dict[a], ++pre[a]);
}
}
}
return res;
}
string abbreviate(string s, int k) {
return (k >= (int)s.size() - ) ? s : s.substr(, k) + to_string((int)s.size() - k - ) + s.back();
}
};
Github 同步地址:
https://github.com/grandyang/leetcode/issues/527
类似题目:
Minimum Unique Word Abbreviation
参考资料:
https://leetcode.com/problems/word-abbreviation/
LeetCode All in One 题目讲解汇总(持续更新中...)
最新文章
- Pipe
- trace enabled
- ODATA WEB API(二)----ODATA服务与客户端
- WCF初探-7:WCF服务配置工具使用
- Spark小课堂Week7 从Spark中一个例子看面向对象设计
- psycopg2关于undefined symbol: lo_truncate64解决方法
- UVa 10405 &; POJ 1458 Longest Common Subsequence
- Nginx编译配置介绍
- 使用ip开头的工具,而不是只会ifconfig
- 像纸质笔记本一样给div,textarea添加行的分割线
- angular6新建项目
- 业务-----添加Service常用逻辑
- kong API gateway
- 图形对象函数figure() 及 子图创建函数subplot()
- kbmMWEncodeEscapes 中汉字编码的问题及解决办法
- android学习-IPC机制之ACtivity绑定Service通信
- October 03rd 2017 Week 40th Tuesday
- div最小高度的2种写法
- 基于jQuery左侧小图滚动右侧大图显示代码
- Python极其简单的分布式异步作业管理系统RQ入门
热门文章
- Appium移动自动化测试-----(三)Intellij IDEA + Android SDK + Genymotion Emulator
- Java中的Object类的几个方法
- Spring Security OAuth2 Demo —— 客户端模式(ClientCredentials)
- 自动轮播swiper css实现
- Docker 指定数据储存目录
- mask-rcnn的解读(三):batch_slice()
- java.lang.NoSuchMethodError的通用解决思路
- logstash将redis中的队列中数据发送到influxdb数据库中
- wpf 打开win8系统软件盘
- SQL行转列,列转行