We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Unique Word Abbreviation

Number: 288

Difficulty: Medium

Paid? Yes

Companies: Google

Problem Description

Given a dictionary of words, implement a class ValidWordAbbr that can tell if a word’s abbreviation is unique. The abbreviation of a word is defined as the concatenation of its first letter, the count of characters between the first and last letters, and its last letter (e.g., "internationalization" becomes "i18n"). A word with only two characters is its own abbreviation. The function isUnique should return true if either no word in the dictionary shares the same abbreviation as the input word, or if all words that share the same abbreviation are exactly the same as the input word.

Key Insights

  • Compute the abbreviation for each word using its first letter, count of characters in-between, and last letter.
  • Use a hash table (dictionary/map) to store each abbreviation as a key and the corresponding word or set of words from the dictionary as the value.
  • When checking if an input word’s abbreviation is unique, verify if the abbreviation is absent in the map or if it exists but only maps to the same word.
  • Care must be taken when handling duplicate words in the dictionary.

Space and Time Complexity

Time Complexity:

  • Constructor: O(N * L) where N is the number of words in the dictionary and L is the average word length.
  • isUnique: O(L), since computing the abbreviation for the input word takes linear time. Space Complexity:
  • O(N * L) in the worst case due to storing abbreviations and corresponding words.

Solution

We use a hash table to map each computed abbreviation to the word from the dictionary if it is unique, or to a special marker (or set) if there are multiple distinct words that share that abbreviation. In the constructor, for each word in the dictionary, we compute its abbreviation. If the abbreviation is not present, we add it with the word as its value. If it is already present and the stored word is different from the current one, we mark this abbreviation as conflicting by storing a value that indicates multiple words (e.g., a special marker like an empty string or a set of words). In the isUnique method, we compute the abbreviation of the input word and check:

  • If the abbreviation does not exist in our map, the input word is unique.
  • If the abbreviation exists and it maps exactly to the input word (and no conflict exists), it is unique.
  • Otherwise, it is not unique. A small nuance is ensuring that duplicate words in the dictionary don’t cause a false conflict.

Code Solutions

# Python solution for ValidWordAbbr
class ValidWordAbbr:
    def __init__(self, dictionary):
        # Store mapping from abbreviation to word or to a conflict marker
        self.abb_map = {}
        for word in dictionary:
            abb = self.get_abbr(word)
            # If the abbreviation is not added yet, set the mapping to the word.
            if abb not in self.abb_map:
                self.abb_map[abb] = word
            else:
                # If the same abbreviation already exists and word is different, mark as conflict.
                if self.abb_map[abb] != word:
                    self.abb_map[abb] = None

    def get_abbr(self, word):
        # For words of length <= 2, abbreviation is the word itself.
        if len(word) <= 2:
            return word
        return word[0] + str(len(word) - 2) + word[-1]

    def isUnique(self, word):
        abb = self.get_abbr(word)
        # If abbreviation is not present, it's unique.
        if abb not in self.abb_map:
            return True
        # Otherwise, check if the stored word is exactly the same as the input word.
        return self.abb_map[abb] == word

# Example usage:
# validWordAbbr = ValidWordAbbr(["deer","door","cake","card"])
# print(validWordAbbr.isUnique("dear"))  # Output: False
← Back to All Questions