288.Unique Word Abbreviation

Tags: [string], [map], [set]

Com: {g}

Link: https://leetcode.com/problems/unique-word-abbreviation/\#/description

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

Solution: Map, Set

class ValidWordAbbr(object):

    def __init__(self, dictionary):
        """
        :type dictionary: List[str]
        """
        self.abbrs = collections.defaultdict(set)
        for w in dictionary:
            self.abbrs[self.get_abbr(w)].add(w)

    def get_abbr(self, word):
        if not word or len(word) < 3:
            return word

        return '{}{}{}'.format(word[0], len(word) - 2, word[-1])


    def isUnique(self, word):
        """
        :type word: str
        :rtype: bool
        """
        abbr = self.get_abbr(word)
        return (abbr not in self.abbrs) or\
               (len(self.abbrs[abbr]) == 1 and word in self.abbrs[abbr])


# Your ValidWordAbbr object will be instantiated and called as such:
# obj = ValidWordAbbr(dictionary)
# param_1 = obj.isUnique(word)

Revelation:

• The graph in the problem description is very confusing. The way to calculate the abbreviation is '{}{}{}'.format(word[0], len(word) - 2, word[-1]).
• The 'unique' here means, the given word's abbreviation is not equal to any dictionary word's abbreviation, or it can equal to some of words' abbreviations, but all these abbreviations should be same, and all these words should be same with the given word.

Note:

• Time complexity of initialization = O(n), n is the number of words in the given dictionary.
• Time complexity of isUnique = O(1).