Domain 2MediumCORE

Unique Word Abbreviation

We are building a class ValidWordAbbr to manage a dictionary of words and determine uniqueness based on their abbreviations.

Domain: Medium•Updated: 2026-08-31
#Algorithms#LeetCode#qwen3.5:9b#Hash Table#Design

288. Unique Word Abbreviation

Model: qwen3.5:9b
Topics: Hash Table,Design
FAANG asked: 1
Acceptance rate: 23.2%


Problem Breakdown

We are building a class ValidWordAbbr to manage a dictionary of words and determine uniqueness based on their abbreviations.

Inputs:

  1. A list of strings (dictionary) during initialization.
  2. A query string (word) for the isUnique method.

Outputs: A boolean indicating if the query word is “unique” relative to the dictionary’s abbreviation rules.

Abbreviation Rules:

  • First char + count of middle chars + last char (e.g., "internationalization" -> "i18n").
  • If length <= 2, it abbreviates to itself (e.g., "it" -> "it").

Uniqueness Conditions for isUnique(word): Returns true if:

  1. No word in the dictionary shares this abbreviation with word.
  2. OR All words in the dictionary that share this abbreviation are identical to word itself (i.e., duplicates of word exist, but no different word exists).

Implicit Constraints: We need efficient lookups since there can be up to 3×1043 \times 10^4 dictionary entries and thousands of queries. We cannot afford an O(N)O(N) scan per query if possible. Edge cases include words with length ≤2\le 2, duplicate inputs in the dictionary, and query strings that match abbreviations but not actual dictionary content.

Intuition

If we simply iterate through the entire dictionary list every time isUnique is called to compute abbreviations and compare them, the complexity per call would be O(N⋅L)O(N \cdot L) where NN is the number of words in the dictionary (30k30k) and LL is word length (20). With 5000 calls, this could lead to roughly 3×1093 \times 10^9 operations, which risks a Time Limit Exceeded.

The key insight is that we can preprocess the dictionary during initialization. We want to group words by their abbreviation so lookups become constant time relative to dictionary size (amortized).

However, simply counting occurrences isn’t enough because of Condition 2: if multiple distinct words map to the same abbreviation, any query with that abbreviation is not unique. If only one distinct word maps to an abbreviation, we must check if the specific word passed matches it exactly.

Therefore, a Hash Map (Dictionary) mapping Abbreviation -> Set of Unique Words seems optimal.

  • During init: Compute abbr for each dict word and add it to its set in the map.
  • During query: Check the map. If the abbreviation doesn’t exist, return True. If it exists but contains only one distinct word that matches our input exactly, return True. Otherwise (multiple words or mismatch), return False.

Approach

  1. Helper Function: Create a helper to compute abbreviations efficiently handling length ≤2\le 2.
  2. Initialization (__init__):
    • Iterate through the provided dictionary list.
    • Compute abbreviation for each word.
    • Store in self.abbr_map: Key = Abbreviation, Value = Set of unique words from dict that produce this abbr. Using a set automatically handles duplicates within the input (e.g., if “deer” appears twice, we only store one instance).
  3. Query (isUnique):
    • Compute abbreviation for word.
    • If not in map: Return True (Condition 1 met).
    • If in map and set size is 1 AND the single word equals word: Return True (Condition 2 met).
    • Otherwise: Return False.

Complexity Analysis

  • Time:
    • Initialization: O(N⋅L)O(N \cdot L) where NN is dictionary length, LL is max word length. We compute abbr for each once.
    • Query (isUnique): O(L)O(L). Computing abbreviation takes linear time with respect to string length (constant 20), and hash map lookup/set check is effectively O(1)O(1) average case.
  • Space: O(N⋅L)O(N \cdot L) to store the abbreviations and sets in the map.

Solution

import collections

class ValidWordAbbr:
    def __init__(self, dictionary):
        # Map abbreviation -> set of unique words from dictionary that produce it
        self.abbr_map = {}
        
        for word in dictionary:
            ab = self.get_abbr(word)
            
            if ab not in self.abbr_map:
                self.abbr_map[ab] = {word}
            else:
                # Add to set; duplicates are handled automatically by the set structure
                self.abbr_map[ab].add(word)

    def get_abbr(self, word):
        length = len(word)
        if length <= 2:
            return word
        
        first_char = word[0]
        last_char = word[-1]
        middle_count = length - 2
        return f"{first_char}{middle_count}{last_char}"

    def isUnique(self, word):
        target_abbr = self.get_abbr(word)
        
        # Condition 1: No dictionary word has this abbreviation
        if target_abbr not in self.abbr_map:
            return True
        
        # Check the set of words that share this abbreviation
        unique_words_in_dict = self.abbr_map[target_abbr]
        
        # If there are multiple distinct words with same abbr, it's never unique.
        # Or if the single word stored is not equal to our query 'word'.
        return len(unique_words_in_dict) == 1 and list(unique_words_in_dict)[0] == word

Edge Cases Handled

  • Short Words (Length ≤\le 2): The get_abbr method explicitly checks length. If a word is “it”, it returns “it”. This ensures the abbreviation logic doesn’t break for short strings where there are no middle characters to count.
  • Duplicate Inputs: Using a Python set in the value of our map handles cases like ["deer", "deer"]. The set will only contain one "deer", ensuring we don’t falsely flag uniqueness based on duplicate entries that represent the same string content.
  • Query Matches Dictionary Word Exactly: If dictionary has ["cake"] and query is "cake", the map contains {c2e: {"cake"}}. The logic checks if set size is 1 AND word matches, returning True. This satisfies Condition 2 of uniqueness (the only conflictors are identical to the input).
  • Query Shares Abbreviation with Different Word: If dictionary has ["deer"] and query is "dear", both map to d2r. The set contains { "deer" }. Since "dear" != "deer", it returns False.