Problem statement not available.
Problem Overview: Design a data structure that checks whether a word’s abbreviation is unique in a given dictionary. The abbreviation rule is simple: keep the first and last character and replace the middle characters with the count (e.g., international → i11l). Words with length ≤ 2 keep the original form.
Approach 1: Brute Force Dictionary Scan (O(n) time per query, O(n) space)
Store all dictionary words in a list or set. When isUnique(word) is called, compute its abbreviation and iterate through the dictionary to check if any other word produces the same abbreviation. If another different word shares that abbreviation, return false. This approach is straightforward but inefficient because each query requires scanning the entire dictionary. With many lookups, the runtime grows quickly.
Approach 2: Hash Map from Abbreviation to Word Set (O(n) build, O(1) average query, O(n) space)
Precompute abbreviations for all dictionary words and store them in a hash map where the key is the abbreviation and the value is a set of words producing that abbreviation. When checking isUnique(word), compute the abbreviation and perform a hash lookup. If the abbreviation does not exist in the map, it is unique. If it exists, the word is unique only when the set contains exactly that same word. This approach relies on fast hash lookups and avoids repeated dictionary scans. It uses a hash table to achieve constant-time checks.
Approach 3: Optimized Hash Map with Conflict Marker (O(n) build, O(1) query, O(n) space)
Instead of storing a full set of words, store a single word per abbreviation. If another different word maps to the same abbreviation, mark the entry as a conflict (for example store an empty string). During isUnique, compute the abbreviation and check the map. If the abbreviation is absent, it is unique. If present, it is unique only when the stored value equals the query word. This reduces memory usage compared to storing sets and keeps lookups constant time. The implementation combines string manipulation with a design-style class structure.
Recommended for interviews: The optimized hash map approach. It demonstrates understanding of preprocessing, constant-time lookups, and efficient data structure design. Brute force shows the basic idea, but interviewers typically expect the hash map solution with O(n) preprocessing and O(1) queries.
According to the problem description, we define a function $abbr(s)$, which calculates the abbreviation of the word $s$. If the length of the word $s$ is less than $3$, then its abbreviation is itself; otherwise, its abbreviation is its first letter + (its length - 2) + its last letter.
Next, we define a hash table $d$, where the key is the abbreviation of the word, and the value is a set, the elements of which are all words abbreviated as that key. We traverse the given word dictionary, and for each word $s$ in the dictionary, we calculate its abbreviation $abbr(s)$, and add $s$ to $d[abbr(s)]$.
When judging whether the word $word$ meets the requirements of the problem, we calculate its abbreviation $abbr(word)$. If $abbr(word)$ is not in the hash table $d$, then $word$ meets the requirements of the problem; otherwise, we judge whether there is only one element in $d[abbr(word)]$. If there is only one element in $d[abbr(word)]$ and that element is $word$, then $word$ meets the requirements of the problem.
In terms of time complexity, the time complexity of initializing the hash table is $O(n)$, where $n$ is the length of the word dictionary; the time complexity of judging whether a word meets the requirements of the problem is $O(1)$. In terms of space complexity, the space complexity of the hash table is $O(n)$.
Java
C++
Go
TypeScript
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Dictionary Scan | O(n) per query | O(n) | Good for understanding the abbreviation rule or when the dictionary is very small |
| Hash Map (Abbreviation → Word Set) | O(n) build, O(1) query | O(n) | General solution when multiple words may share the same abbreviation |
| Optimized Hash Map with Conflict Marker | O(n) build, O(1) query | O(n) | Best practical approach; minimal memory and constant-time lookup |
The Hardest EASY Coding Question Ever - Valid Word - Leetcode 3136 • Greg Hogg • 221,977 views views
Watch 9 more video solutions →Practice Unique Word Abbreviation with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor