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:
- A list of strings (
dictionary) during initialization. - A query string (
word) for theisUniquemethod.
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:
- No word in the dictionary shares this abbreviation with
word. - OR All words in the dictionary that share this abbreviation are identical to
worditself (i.e., duplicates ofwordexist, but no different word exists).
Implicit Constraints: We need efficient lookups since there can be up to dictionary entries and thousands of queries. We cannot afford an scan per query if possible. Edge cases include words with length , 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 where is the number of words in the dictionary () and is word length (20). With 5000 calls, this could lead to roughly 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, returnTrue. Otherwise (multiple words or mismatch), returnFalse.
Approach
- Helper Function: Create a helper to compute abbreviations efficiently handling length .
- 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).
- 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: ReturnTrue(Condition 2 met). - Otherwise: Return
False.
- Compute abbreviation for
Complexity Analysis
- Time:
- Initialization: where is dictionary length, is max word length. We compute abbr for each once.
- Query (
isUnique): . Computing abbreviation takes linear time with respect to string length (constant 20), and hash map lookup/set check is effectively average case.
- Space: 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 2): The
get_abbrmethod 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
setin 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, returningTrue. 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 tod2r. The set contains{ "deer" }. Since"dear"!="deer", it returnsFalse.