288. Unique Word Abbreviation

Problem Description

The problem involves creating a class called ValidWordAbbr that can store a dictionary of words and check if a given word's abbreviation is unique within that dictionary. An abbreviation of a word consists of its first letter, the number of characters between the first and last letter, and its last letter. If a word is only two characters long, the abbreviation is the word itself.

To clarify:

• The abbreviation for "dog" is "d1g".
• The abbreviation for "internationalization" is "i18n".
• The abbreviation for "it" is "it" itself.

The ValidWordAbbr class should support the following operations:

• Initialization (__init__): When an instance of ValidWordAbbr is created, it is initialized with a given list of words, which is referred to as the dictionary.

• Check Uniqueness (isUnique): This method checks whether a word's abbreviation is unique. A word's abbreviation is considered unique if no other word in the dictionary has the same abbreviation or if the only word in the dictionary with the same abbreviation is the word itself.

Intuition

To solve the problem efficiently, we can use a dictionary (a hash map) to store abbreviations of the words in the given dictionary with their corresponding words.

Here's the thought process to arrive at the solution:

• Storing Abbreviations: We need a way to conveniently check if the abbreviation of a given word is unique among the stored words. Therefore, we can store the abbreviations in a way that allows us to quickly lookup which words share the same abbreviation.

• Using Sets for Words: For each abbreviation, we might have multiple words corresponding to it in the dictionary. We use a set to store these words to avoid duplicates and enable fast existence checks.

• Checking Uniqueness: When checking the uniqueness of the abbreviation of a given word, there are two conditions to consider:

  1. The abbreviation does not exist in our stored abbreviations. This guarantees uniqueness.
  2. The abbreviation exists, but it is linked exclusively to the given word.

• Edge Cases: We don't need to store abbreviations for words of length two or less since they are abbreviations of themselves and cannot conflict with others.

Implementing the above logic results in the provided solution, where:

• The __init__ function creates a hash table to store the words with their abbreviations as keys.
• The word_abbr helper function generates the abbreviation for any given string.
• The isUnique function uses word_abbr to check the conditions that classify the abbreviation as unique.

Solution Approach

The solution makes use of a hash table and sets to efficiently store and query word abbreviations.

• Initializing the Object:

  • A defaultdict of sets is used to store the words against their abbreviations. defaultdict is a subclass of dict which provides a default value for a key that does not exist.
  • Upon initialization (__init__ method), the dictionary takes each word and computes its abbreviation using a helper function (word_abbr).
  • The abbreviated form of the word is used as a key, and the word itself is added to the set corresponding to that key.

• Abbreviating the Word:

  • The helper function word_abbr creates an abbreviation by taking the first and last character of the word and the count of the characters in between.
  • The abbreviation is formed as first_char + (len(word) - 2) + last_char.
  • If the word is shorter than 3 characters, the word itself is returned as its abbreviation.

• Checking Uniqueness:

  • isUnique checks if a given word's abbreviated form is unique in the dictionary.
  • First, it computes the abbreviation of the word to be checked.
  • Then it retrieves the set of words that share the same abbreviation from our hash table.
  • If this set is empty, no words in our dictionary have the same abbreviation, and it returns True.
  • If the set contains only the given word, this again ensures uniqueness, and it returns True.
  • The check len(words) == 1 and word in words ensures that the word's set contains exactly one word and that the word is the one we are checking.
  • Otherwise, the word is not unique, and it returns False.

Here is how the core part of the implementation connects to the solution approach:

1class ValidWordAbbr:
2    def __init__(self, dictionary: List[str]):
3        self.words = defaultdict(set)
4        for word in dictionary:
5            abbr = self.word_abbr(word)       # Compute the abbreviation
6            self.words[abbr].add(word)        # Map it with the word in set
7
8    def isUnique(self, word: str) -> bool:
9        abbr = self.word_abbr(word)           # Abbreviation for the word
10        words = self.words[abbr]              # Get the set of words with same abbreviation
11        return not words or (len(words) == 1 and word in words) # Check for uniqueness
12
13    def word_abbr(self, s):
14        return s if len(s) < 3 else f'{s[0]}{len(s) - 2}{s[-1]}' # Helper function

By using a hash table and sets, the solution efficiently supports both the addition of words to the dictionary and the uniqueness check, optimizing for quick lookups and taking advantage of the fact that sets offer constant time complexity for insertion and lookup operations.

Example Walkthrough

We'll illustrate how the ValidWordAbbr class operates using a small example. Let's say we want to initialize our dictionary with the words ["deer", "door", "cake", "card"]. We'll then check the uniqueness of certain abbreviations.

Initialization

When we create an instance of ValidWordAbbr with our dictionary, it will process each word and store its abbreviation:

• "deer" -> "d2r"
• "door" -> "d2r"
• "cake" -> "c2e"
• "card" -> "c2d"

Our hash table for storing abbreviations and corresponding words will look like this:

1{
2  "d2r": {"deer", "door"}, // Both "deer" and "door" abbreviate to "d2r"
3  "c2e": {"cake"},         // "cake" abbreviates to "c2e"
4  "c2d": {"card"}          // "card" abbreviates to "c2d"
5}

Checking Uniqueness

Let's check the uniqueness of the word "dear":

1. Calculate its abbreviation: "dear" -> "d2r"
2. Check if "d2r" is in our hash table. It is, and its value is the set {"door", "deer"}.
3. Since "dear" is not in this set and the set contains more than one element, "d2r" is not unique to "dear".
4. Therefore, isUnique("dear") returns False.

Now, let's check the uniqueness of the word "cart":

1. Calculate its abbreviation: "cart" -> "c2t"
2. Check if "c2t" is in our hash table. It isn't.
3. Since there are no words in our dictionary that abbreviate to "c2t", the abbreviation is unique.
4. Thus, isUnique("cart") returns True.

Lastly, let's check the uniqueness of the word "cake":

1. Calculate its abbreviation: "cake" -> "c2e"
2. Look up "c2e" in our hash table. We find the set {"cake"}.
3. Since "cake" is in this set and it is the only element, its abbreviation is unique to "cake".
4. Hence, isUnique("cake") returns True.

This example demonstrates how ValidWordAbbr uses a hash table and sets to efficiently store word abbreviations and determine the uniqueness of a word's abbreviation within the dictionary.

Solution Implementation

Time and Space Complexity

Time Complexity

• __init__ function:

  • The constructor iterates through each word in the given dictionary to compute its abbreviation and store it. If n is the number of words and k is the average length of the words, the time complexity is O(n*k) because the abbreviation process for each word takes O(k) time, and it is done for all n words.

• isUnique function:

  • This function computes the abbreviation of the input word (which takes O(k) time, where k is the length of the word), and then it checks whether this word is unique based on the abbreviation look-up in the dictionary. The look-up time in a hash table is O(1) on average, but in the worst case (if there are hash collisions), it could be O(n) where n is the number of elements in the hash table under the same hash bucket. Because we need to check if the word is in the set, this takes O(1) time on average if sets are implemented with a hash. Thus, the time complexity is O(k) on average.

Space Complexity

• __init__ function:

  • The space complexity is O(n*k) because each word is stored in the set data structure, and there may be n words of average length k. In cases where the dictionary contains many words with the same abbreviation but they are different words, this might not be efficient.

• isUnique function:

  • The space complexity is O(1) because no additional space is used besides the input word and the space used by the abbreviation. This does not grow with the size of the input dictionary.

Please note that the abbreviation calculation itself is considered a constant-time operation because although it varies with the length of the input word, it is bounded and does not grow with the size of the dictionary.

Learn more about how to find time and space complexity quickly using problem constraints.