# C++ Divide and conquer 63ms beats 89%

• First, put the same length in one group, then solve this group by find unique abbreviation.

``````vector<string> wordsAbbreviation(vector<string>& dict) {
unordered_map<int,vector<int>> map;
for(int i=0;i<dict.size();i++)map[dict[i].length()].push_back(i);
vector<string> result(dict.size(),"");
for(auto x:map)get_abbreviation(dict,x.second,x.first,result);
return result;
}

void get_abbreviation(vector<string> &dict,vector<int> &index,int l,vector<string> &result)
{
if(l<4)
{
for(int i=0;i<index.size();i++)result[index[i]]=dict[index[i]];
return;
}
int i=0,n=index.size();;
vector<bool> vis(index.size(),true);
while(i<l-2 &&n>0)
{
unordered_map<string,vector<int>> map;
for(int j=0;j<index.size();j++)if(vis[j])map[dict[index[j]].substr(0,i)+dict[index[j]][l-1]].push_back(j);
for(auto x:map)
{
if(x.second.size()==1)
{
vis[x.second[0]]=false;n--;
string temp=dict[index[x.second[0]]];
if(i==0)result[index[x.second[0]]]=temp.substr(0,1)+to_string(l-2)+temp.substr(l-1,1);
else result[index[x.second[0]]]=temp.substr(0,i)+to_string(l-1-i)+temp.substr(l-1,1);
}
}
i++;
}
for(int j=0;j<index.size();j++)if(vis[j])result[index[j]]=dict[index[j]];
}
``````

};

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.