原题单词缩写
给出一组 n 个不同的非空字符串，您需要按以下规则为每个单词生成 最小 的缩写。
- 从第一个字符开始，然后加上中间缩写掉的字符的长度，后跟最后一个字符。
- 如果有冲突，就是多个单词共享相同的缩写，使用较长的前缀，而不是仅使用第一个字符，直到使单词的缩写的映射变为唯一。 换句话说，最终得到的缩写不能映射到多个原始单词。
- 如果缩写不会使单词更短，则不进行缩写，保持原样。
审题
- 首先这题的有个地方说得不清楚，就是解决冲突的方式。比如iabcx和idefx冲突了，因为缩写都是i3x,这时需要把这两个都加长前缀，变成ia2x和id2x。重点在于两者都变化。应用到整个集合里，当有其他单词和你冲突时，你就要增大前缀，知道没有单词和你冲突。
- 我看了下题目的标签，里有个排序，顺着这个思路想了下：
只有后缀相同的单词之前会可能冲突，因为后缀一定保留
只有长度相同的会冲突。证明：如果长度不同的单词缩写到长度相同，那么缩写掉部分的长度肯定不同，那么中间的数字肯定不同，那么这两个缩写肯定不同，不会冲突。
所以只有长度相同且后缀相同的单词才会冲突，所以把这些可能冲突的分到一个组里。
- 经过2的处理，同一个组里，都是有冲突隐患的单词。对于某一个单词，要保留多长的前缀才可以呢？它和组内的其他单词比较共同前缀，假如最长共同前缀为k,那么它就保留到k+1,因为到k+1的这一段，所有其他的都会跟它呈现出不同。如果直接照着这个直接实现，复杂度是O(n^2),n是组内的单词个数，有没有办法直接找到最长共同前缀呢？直接使用字符串的排序，字符串本身的比较方法是从前往后逐个比较字符，所以具有更多共同前缀的单词会贴到一起。
- 证明如下：
假设排序后单词k和k-1的共同前缀长度是x,单词k和k+1的共同长度是y, 如果最长共同前缀不是x或y,那么存在一个单词t，它不在k的两边，且共同前缀z满足：z>x，z>y。
单词k+1在k的后面，且共同前缀是y,说明：k+1[y+1]>k[y+1];同理对于k-1有：k-1[x+1]<k[x+1]。而z>x且z>y,那么这两个式子对于t也是成立的，也就是在排序后t会在k-1和k+1之间，而这时不可能的，所以出现错误假设不成立，不存在这样的t。
简单说，公共前缀越长，排序后越靠近。所以每个单词只需要取左右相邻单词的共同前缀作为参考即可。
代码：
//对单词排序，按长度、后缀和单词本身的先后顺序
//这样长度相同、后缀相同的单词会分到一起
bool wordPairCmp(pair<string, int>& wp1, pair<string, int> &wp2){
int result = (int)wp1.first.length()-(int)wp2.first.length();
if (result!=0) return result<0;
result = wp1.first.back()-wp2.first.back();
if (result!=0) return result<0;
return wp1.first.compare(wp2.first)<0;
}
//求共同前缀的长度
inline int prefixLapCount(string &s1, string &s2){
int c = 0;
while (s1[c] == s2[c]) {
c++;
}
return c;
}
//把一个单词按指定前缀长度缩写
inline void wordAbb(string &originalWord, int prefixCount){
int len = (int)originalWord.length();
int cut = len-prefixCount-1;
if (cut<=1) {
return;
}
int destLen = prefixCount+1+log10(cut)+1;
int preIdx = len-cut-2;
string abb(destLen,' ');
for (int i = 0; i<=preIdx; i++) {
abb[i] = originalWord[i];
}
abb[destLen-1] = originalWord.back();
//中间缩写的数字部分，没有使用atoi等方法而是直接实现，效率会快很对
for (int i = destLen-2; i>preIdx; i--) {
abb[i] = cut%10+'0';
cut = cut/10;
}
originalWord = abb;
}
vector<string> wordsAbbreviation(vector<string> &dict) {
//使用pair的原因是为了记录单词在原数组里的索引位置，这样排序后，还可以再重置到输入时的顺序
vector<pair<string, int>> wordPairs;
int i = 0;
for (auto &w : dict){
wordPairs.push_back({w,i});
i++;
}
sort(wordPairs.begin(), wordPairs.end(), wordPairCmp);
int size = (int)wordPairs.size();
int preLapCount = 0; //和前一个重叠的字符个数
for (int i = 0; i<size; i++) {
int nextLapCount = 0;
//因为没有使用分组，即没有用多维数组，而是单个数组，所以需要做前后判定，长度不同或者后缀不同，则共同前缀就不考虑了，直接是0.
//这里会影响效率，因为大部分比较都是无意义的或者说跟排序的工作有重复
if (i<size-1 &&
wordPairs[i].first.length() == wordPairs[i+1].first.length() &&
wordPairs[i].first.back() == wordPairs[i+1].first.back()) {
nextLapCount = prefixLapCount(wordPairs[i].first, wordPairs[i+1].first);
}
wordAbb(wordPairs[i].first, max(preLapCount, nextLapCount)+1);
preLapCount = nextLapCount;
}
for (auto &p : wordPairs){
dict[p.second] = p.first;
}
return dict;
}
