C++ easy to understand (one unordered_set, one unordered_map)


  • 0

    Example 1 (returns true):
    dictionary = ["hello", "hello"], word = "hello"
    the de-duplicated dict = ["hello"]
    abbrs map = ["h3o", 1]
    word "hello" is found in dict, which means its abbr count must be 1, otherwise it means there are other words in dict that maps to "h3o".

    Example 2 (returns false):
    dictionary = ["hello", "hello"], word = "hallo"
    the de-duplicated dict = ["hello"]
    abbrs map = ["h3o", 1]
    word "hallo" is not found in dict, and its abbreviation is "h3o", which means there must not be any "h3o" in the abbrs map, but there is (count = 1), hence returns false.

    class ValidWordAbbr {
    private:
        string getAbbr(const string &str) {
            int n = str.size();
            if (n <= 2)
                return str;
            
            return str[0] + to_string(n-2) + str[n-1];
        }
        
        unordered_set<string> dict; // deduplicated dictionary
        unordered_map<string, int> abbrs; // map of abbr to its count
    public:
        ValidWordAbbr(vector<string> &dictionary) {
            for (const string &str : dictionary)
                dict.insert(str);
                
            for (const string &str : dict)
                abbrs[getAbbr(str)] ++;
        }
    
        bool isUnique(string word) {
            if (dict.find(word) != dict.end()) // if word is one of the original dict words, its abbr count must be 1 (i.e. the original count)
                return abbrs[getAbbr(word)] == 1;
            else // if word is not one of the original dict words, no same abbr is allowed
                return abbrs[getAbbr(word)] == 0;
        }
    };
    

Log in to reply
 

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