C++ Divide and conquer 63ms beats 89%


  • 0
    B

    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]];
    }
    

    };


Log in to reply
 

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