288 Unique Word Abbreviation

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 nootherword 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
  • Simple map abr -> word, and then follow some boolean logic to check if it the abbreviation of a given string exists in the given dictionary.

class ValidWordAbbr {
public:
    ValidWordAbbr(vector<string> &dictionary)
    {
        for (string s : dictionary) {
            string temp = *s.begin() +
                to_string(s.length() - 2) +
                *s.rbegin();

            // found
            if (abr_words.find(temp) != abr_words.end()) {
                abr_words[temp].insert(s);
            }

            // not found
            else 
            {
                unordered_set<string> temp_set;
                temp_set.insert(s);
                abr_words.insert(make_pair(temp, temp_set));
            }
        }
    }

    bool isUnique(string word)
    {
        // A word's abbreviation is unique if no other word from the dictionary 
        // has the same abbreviation.
        string temp = *word.begin() + 
            to_string(word.length() - 2) + 
            *word.rbegin();

        // no other word has the same abbreviation
        if (abr_words.find(temp) == abr_words.end()) return true;

        // other word has the same abbreviation
        else if (abr_words.find(temp) != abr_words.end()
            && abr_words[temp].find(word) != abr_words[temp].end()
            && abr_words[temp].size() == 1) return true;
        return false;
    }

private:
    // < abr , word >
    unordered_map<string, unordered_set<string>> abr_words;
};

Last updated