288. Unique Word Abbreviation

• Difficulty: Medium

• Topics: Hash Table, Design

• Similar Questions:

  • Two Sum III - Data structure design

  • Generalized Abbreviation

Problem:

An abbreviation of a word follows the form <first letter><number><last letter>. Below are some examples of word abbreviations:

a) it                      --> it    (no abbreviation)

     1
     ↓
b) d|o|g                   --> d1g

              1    1  1
     1---5----0----5--8
     ↓   ↓    ↓    ↓  ↓    
c) i|nternationalizatio|n  --> i18n

              1
     1---5----0
     ↓   ↓    ↓
d) l|ocalizatio|n          --> l10n

Assume you have a dictionary and given a word, find whether its abbreviation is unique in the dictionary. A word's abbreviation is unique if no other word from the dictionary has the same abbreviation.

Example:

Given dictionary = [ "deer", "door", "cake", "card" ]

isUnique("dear") -> false
isUnique("cart") -> true
isUnique("cane") -> false
isUnique("make") -> true

Solutions:

class ValidWordAbbr {
public:
    ValidWordAbbr(vector<string>& dictionary) {
        words.insert(dictionary.begin(), dictionary.end());

        for (const auto& word : words) {
            string abbr = toAbbr(word);
            ++wordAbbrFreq[abbr];
        }
    }

    bool isUnique(const string& word) {
        if (words.count(word) > 0) {
            return wordAbbrFreq[toAbbr(word)] == 1;
        } else {
            return wordAbbrFreq.find(toAbbr(word)) == wordAbbrFreq.end();
        }
    }
private:
    string toAbbr(const string& str) {
        string abbr;
        abbr.push_back(str[0]);
        if (str.length() > 2) {
            abbr.append(to_string(str.length() - 2));
        }
        if (str.length() > 1) {
            abbr.push_back(str.back());
        }

        return abbr;
    }

    unordered_set<string> words;
    unordered_map<string, int> wordAbbrFreq;

};

/**
 * Your ValidWordAbbr object will be instantiated and called as such:
 * ValidWordAbbr* obj = new ValidWordAbbr(dictionary);
 * bool param_1 = obj->isUnique(word);
 */