A C++ solution beats 96% performance


  • 1
    L

    Since we are talking about words, and words are only composed from at most 52 characters ('a'-'z' and 'A'-'Z'). So we can create a 52x52 2-D matrix to store abbreviations, eg. the abbreviation of "carb" is "c2b", which can be represented as:

      a b c d ... 
    a     | 
    b -- -2
    c
    d
    ...
    

    By following this scheme, word searching and abbreviating will be quite straight forward.

    class ValidWordAbbr {
    public:
        ValidWordAbbr(vector<string> &dictionary) {
            int nwd(dictionary.size());
            mp_str.resize(52*52);
            mp_abr.resize(52*52);
            ia = (int)'a';
            iz = (int)'z';
            iA = (int)'A';
            iZ = (int)'Z';
            
            for (int is(0);is<nwd;is++) {
                if (dictionary[is].size()<=2) continue; 
                char chr1(dictionary[is][0]);
                char chr2(dictionary[is][dictionary[is].size()-1]);
                mp_abr[remap(chr1,chr2)].push_back(dictionary[is].size()-2);
                mp_str[remap(chr1,chr2)].push_back(dictionary[is]);
            }
        }
    
        bool isUnique(string word) {
            if (!word.size() || word.size()<=2) return true;
            char chr1(word[0]);
            char chr2(word[word.size()-1]);
            int ind(remap(chr1,chr2));
            if (!mp_abr[ind].size()) return true;
            for (int i(0);i<mp_abr[ind].size();i++) {
                if (mp_abr[ind][i]==word.size()-2 && mp_str[ind][i]!=word) return false;
            }
            return true;
        }
        
    private:
       vector <vector <int> > mp_abr;
       vector <vector <string> > mp_str;
       int ia,iz;
       int iA,iZ;
       
       int remap(char chr1, char chr2) {
           return index(chr1)*52+index(chr2);
       }
       
       int index(char chr) {
           int ic=(int)chr;
           if (ic>=ia && ic<=iz) return (ic-ia);
           if (ic>=iA && ic<=iZ) return (ic-iA)+26;
       }
       
    };

Log in to reply
 

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