​LeetCode刷题实战527：单词缩写

示例:
输入: ["like", "god", "internal", "me", "internet", "interval", "intension", "face", "intrusion"]
输出: ["l2e","god","internal","me","i6t","interval","inte4n","f2e","intr4n"]
 
注意:
n和每个单词的长度均不超过 400。
每个单词的长度大于 1。
单词只由英文小写字母组成。
返回的答案需要和原数组保持同一顺序。

// 字典树类
class Trie{
public:
    Trie* next[26] = {NULL}; //字典树的26个字数，代表26的字母'a'-'z'
    int cnt = 0; //拥有该前缀的单词数量
    void insert(string& s){ //字典树的插入函数，用于在字典树中插入单词s
        Trie* t = this;

        for(int i=0; i<s.size(); i++){
            if(t->next[s[i]-'a'] == NULL) //若节点不存在，则创建节点
                t->next[s[i]-'a'] = new Trie();
            t = t->next[s[i]-'a'];
            t->cnt++; //拥有该前缀的单词数量+1
        }
    } 
};

class Solution {
public:
    vector<string> wordsAbbreviation(vector<string>& dict) {
        int n = dict.size(); //单词数量
        unordered_map<string, vector<string>> group; //分组所用容器
        unordered_map<string, int> pos; //记录原始单词表dict每个单词的位置
        vector<string> ans(n); //存储单词列表缩写

        for(int i=0; i<n; i++){ //分组操作
            int m = dict[i].size(); //每个单词的长度
            string tmp = dict[i][0] + to_string(m) + dict[i][m-1]; //每个单词的缩写
            group[tmp].push_back(dict[i]); //根据每个单词缩写进行分组
            pos[dict[i]] = i; //记录原始单词列表dict每个单词的原始位置
        }

        unordered_map<string, vector<string>>::iterator it; //迭代器
        for(it=group.begin(); it!=group.end(); it++){ //遍历group it->first对应每个缩写 it->second对应该缩写下的所有单词
            vector<string> strs = it->second; //获取该缩写下所有单词
            int m = strs.size(); //该缩写下所有单词数量
            Trie *p = new Trie(), *q; //建立字典树

            for(int i=0; i<m ;i++)
                p->insert(strs[i]); //将单词插入字典树

            for(int i=0; i<m; i++){
                q = p;
                string tmp; //记录单词的缩写形式

                //根据字典树前缀判断单词缩写形式
                for(int j=0; j<strs[i].size(); j++){
                    //若该前缀下单词只有一个
                    if(q->next[strs[i][j]-'a']->cnt==1){
                        //可缩写的字符数量
                        int k = strs[i].size()-j-2;

                        //若可缩写的字符数量大于1，则进行缩写，否则保持单词原型不变
                        if(k>1)
                            tmp += strs[i][j] + to_string(k) + strs[i][strs[i].size()-1];
                        else
                            tmp = strs[i];

                        break;
                    }
                    
                    tmp += strs[i][j]; //单词前缀增加
                    q = q->next[strs[i][j]-'a']; 
                }
                ans[pos[strs[i]]] = tmp; //根据pos中每个单词的原始位置，存放单词的缩写形式
            }
        }

        return ans;
    }
};