Share my C++ solution using hash map, no DFS


  • 0
    S
    class Solution{
    public:
        string minAbbreviation(string target, vector<string>& dictionary){
            int len=target.size();
            unordered_set<string> Set;
            for(string ss : dictionary)if(ss.size()==len)Set.insert(ss);
            if(Set.empty())return to_string(len);
            unordered_map<int,unordered_set<string>> Map;
            Map[1].insert(to_string(len));
            for(int i=1;i<=len;i++){
                for(string ss : Map[i]){
                    if(IsUnique(ss,Set))return ss;
                    Generate(ss,Map);  //generate longer abbreviations from ss
                }
            }
            return target;
        }
        bool IsUnique(string ss,unordered_set<string>& Set){
            for(string tmps : Set){
                int j=0;
                bool unmatch=false;
                for(int i=0;i<ss.size();i++){
                    if(ss[i]<='9'){
                        int tmpnum=0;
                        while(i<ss.size()&&ss[i]<='9')tmpnum=10*tmpnum+ss[i++]-'0';
                        i--;
                        j+=tmpnum;
                    }else{
                        if(ss[i]!=tmps[j++]){
                            unmatch=true;
                            break;
                    }
                }
                if(unmatch)continue;
                return false;
            }
            return true;
        }
        void Generate(string& ss,string& target,unordered_map<int,unordered_set>& Map){
            int i=0,tmpnum=0;
            //always put one letter back into the foremost number
            if(ss[i]>'9')return;
            while(i<ss.size()&&ss[i]<='9')tmpnum=10*tmpnum+ss[i++]-'0';
            for(int j=0;j<tmpnum;j++){
                string trystring;
                if(j==0)trystring=target[0]+(tmpnum-1==0? "":to_string(tmpnum-1))+ss.substr(i);
                else if(j==tmpnum-1)trystring=to_string(tmpnum-1)+target[j]+ss.substr(i);
                else trystring=to_string(j)+target[j]+to_string(tmpnum-1-j)+ss.substr(i);
                Map[getSize(trystring)].insert(trystring);
            }
        }
        int getSize(string ss){
            int len=0;
            for(int i=0;i<ss.size();i++){
                if(ss[i]<='9'){
                    while(ss[i]<='9')i++;
                    i--;
                }
                len++;
            }
            return len;
        }
    };

Log in to reply
 

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