LeetCode 527. 单词缩写（Trie树）

示例:
输入: ["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};
    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:
    vector<string> wordsAbbreviation(vector<string>& dict) {
        unordered_map<string, vector<string>> group;
        unordered_map<string, int> 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<string> 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;
    }
};