本文共 2401 字，大约阅读时间需要 8 分钟。

1. 题目

给定一个由n个不重复非空字符串组成的数组，你需要按照以下规则为每个单词生成最小的缩写。

• 初始缩写由起始字母+省略字母的数量+结尾字母组成。
• 若存在冲突，亦即多于一个单词有同样的缩写，则使用更长的前缀代替首字母，直到从单词到缩写的映射唯一。换而言之，最终的缩写必须只能映射到一个单词。
• 若缩写并不比原单词更短，则保留原样。

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

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/word-abbreviation

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 解题

• 对字符串进行分组（首尾字符+长度），这种情况，缩写才可能一样
• 组内单词插入trie树，记录每个节点的占用次数，如果只出现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
   
     wordsAbbreviation(vector
    
     & dict) {
           unordered_map
     
      > group;        unordered_map
      
        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
       
         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;    }};
       
      
     
    
   

332 ms 330.2 MB

我的CSDN

长按或扫码关注我的公众号（Michael阿明），一起加油、一起学习进步！

转载地址：https://michael.blog.csdn.net/article/details/107951276 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！