算法：单词缩写

原题单词缩写

给出一组 n 个不同的非空字符串，您需要按以下规则为每个单词生成 最小 的缩写。

• 从第一个字符开始，然后加上中间缩写掉的字符的长度，后跟最后一个字符。
• 如果有冲突，就是多个单词共享相同的缩写，使用较长的前缀，而不是仅使用第一个字符，直到使单词的缩写的映射变为唯一。 换句话说，最终得到的缩写不能映射到多个原始单词。
• 如果缩写不会使单词更短，则不进行缩写，保持原样。

审题

1. 首先这题的有个地方说得不清楚，就是解决冲突的方式。比如iabcx和idefx冲突了，因为缩写都是i3x,这时需要把这两个都加长前缀，变成ia2x和id2x。重点在于两者都变化。应用到整个集合里，当有其他单词和你冲突时，你就要增大前缀，知道没有单词和你冲突。
2. 我看了下题目的标签，里有个排序，顺着这个思路想了下：

• 只有后缀相同的单词之前会可能冲突，因为后缀一定保留

• 只有长度相同的会冲突。证明：如果长度不同的单词缩写到长度相同，那么缩写掉部分的长度肯定不同，那么中间的数字肯定不同，那么这两个缩写肯定不同，不会冲突。

  所以只有长度相同且后缀相同的单词才会冲突，所以把这些可能冲突的分到一个组里。

3. 经过2的处理，同一个组里，都是有冲突隐患的单词。对于某一个单词，要保留多长的前缀才可以呢？它和组内的其他单词比较共同前缀，假如最长共同前缀为k,那么它就保留到k+1,因为到k+1的这一段，所有其他的都会跟它呈现出不同。如果直接照着这个直接实现，复杂度是O(n^2),n是组内的单词个数，有没有办法直接找到最长共同前缀呢？直接使用字符串的排序，字符串本身的比较方法是从前往后逐个比较字符，所以具有更多共同前缀的单词会贴到一起。
4. 证明如下：

  假设排序后单词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;
}