Simple C++ Solution that beats 100% (156ms)


  • 1
    H

    The key is that we don't really need to store the abbreviation string directly. With just the word length, first and last characters, we can decide if two words have the same abbreviation.

    Furthermore, we can construct a hash value from length, first and last characters. With this we can use the integer key map, which is much faster.

    class ValidWordAbbr {
    public:    
        ValidWordAbbr(vector<string> &dictionary) {
            for(auto& s : dictionary) {
                auto index = hash(s); 
                // if we encounter the same abbreviation twice, they can never be unique
                // use empty string to indicate this
                if(m.count(index) && m[index] != s)
                    m[index].clear();
                else 
                    m[index] = s;
            }
        }
    
        bool isUnique(string s) {
            if(s.empty()) return true;
            auto index = hash(s);
            if(!m.count(index)) return true;
            if(m[index].empty()) return false;
            return m[index] == s;
        }
        
    private:
        index_t hash(string& s) const {
            // the range of alphabets can be represented with less than 100 integers
            return (index_t)(s.front()-'A') * 100 + (index_t)(s.back()-'A') + s.length() * 10000;;
        }    
    
    private:
        typedef unsigned long long index_t;
        unordered_map<index_t,string> m;
    };

Log in to reply
 

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