?LeetCode刷題實戰(zhàn)527：單詞縮寫

示例:
輸入: ["like", "god", "internal", "me", "internet", "interval", "intension", "face", "intrusion"]
輸出: ["l2e","god","internal","me","i6t","interval","inte4n","f2e","intr4n"]
?
注意:
n和每個單詞的長度均不超過 400。
每個單詞的長度大于 1。
單詞只由英文小寫字母組成。
返回的答案需要和原數(shù)組保持同一順序。

// 字典樹類
class?Trie{
public:
????Trie* next[26] = {NULL}; //字典樹的26個字?jǐn)?shù)，代表26的字母'a'-'z'
????int?cnt = 0; //擁有該前綴的單詞數(shù)量
????void?insert(string& s){ //字典樹的插入函數(shù)，用于在字典樹中插入單詞s
????????Trie* t = this;

????????for(int?i=0; i????????????if(t->next[s[i]-'a'] == NULL) //若節(jié)點不存在，則創(chuàng)建節(jié)點
????????????????t->next[s[i]-'a'] = new?Trie();
????????????t = t->next[s[i]-'a'];
????????????t->cnt++; //擁有該前綴的單詞數(shù)量+1
????????}
????} 
};

class?Solution?{
public:
????vector<string> wordsAbbreviation(vector<string>& dict) {
????????int?n = dict.size(); //單詞數(shù)量
????????unordered_map<string, vector<string>> group; //分組所用容器
????????unordered_map<string, int> pos; //記錄原始單詞表dict每個單詞的位置
????????vector<string> ans(n); //存儲單詞列表縮寫

????????for(int?i=0; i//分組操作
????????????int?m = dict[i].size(); //每個單詞的長度
????????????string?tmp = dict[i][0] + to_string(m) + dict[i][m-1]; //每個單詞的縮寫
????????????group[tmp].push_back(dict[i]); //根據(jù)每個單詞縮寫進(jìn)行分組
????????????pos[dict[i]] = i; //記錄原始單詞列表dict每個單詞的原始位置
????????}

????????unordered_map<string, vector<string>>::iterator it; //迭代器
????????for(it=group.begin(); it!=group.end(); it++){ //遍歷group it->first對應(yīng)每個縮寫 it->second對應(yīng)該縮寫下的所有單詞
????????????vector<string> strs = it->second; //獲取該縮寫下所有單詞
????????????int?m = strs.size(); //該縮寫下所有單詞數(shù)量
????????????Trie *p = new?Trie(), *q; //建立字典樹

????????????for(int?i=0; i????????????????p->insert(strs[i]); //將單詞插入字典樹

????????????for(int?i=0; i????????????????q = p;
????????????????string?tmp; //記錄單詞的縮寫形式

????????????????//根據(jù)字典樹前綴判斷單詞縮寫形式
????????????????for(int?j=0; j????????????????????//若該前綴下單詞只有一個
????????????????????if(q->next[strs[i][j]-'a']->cnt==1){
????????????????????????//可縮寫的字符數(shù)量
????????????????????????int?k = strs[i].size()-j-2;

????????????????????????//若可縮寫的字符數(shù)量大于1，則進(jìn)行縮寫，否則保持單詞原型不變
????????????????????????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; //根據(jù)pos中每個單詞的原始位置，存放單詞的縮寫形式
????????????}
????????}

????????return?ans;
????}
};