The abbreviation of a word is a concatenation of its first letter, the number of characters between the first and last letter, and its last letter. If a word has only two characters, then it is an abbreviation of itself.
For example:
dog --> d1g because there is one letter between the first letter 'd' and the last letter 'g'.internationalization --> i18n because there are 18 letters between the first letter 'i' and the last letter 'n'.it --> it because any word with only two characters is an abbreviation of itself.Implement the ValidWordAbbr class:
ValidWordAbbr(String[] dictionary) Initializes the object with a dictionary of words.boolean isUnique(string word) Returns true if either of the following conditions are met (otherwise returns false):
dictionary whose abbreviation is equal to word's abbreviation.dictionary whose abbreviation is equal to word's abbreviation, that word and word are the same.
Example 1:
Input
["ValidWordAbbr", "isUnique", "isUnique", "isUnique", "isUnique", "isUnique"]
[[["deer", "door", "cake", "card"]], ["dear"], ["cart"], ["cane"], ["make"], ["cake"]]
Output
[null, false, true, false, true, true]
Explanation
ValidWordAbbr validWordAbbr = new ValidWordAbbr(["deer", "door", "cake", "card"]);
validWordAbbr.isUnique("dear"); // return false, dictionary word "deer" and word "dear" have the same abbreviation "d2r" but are not the same.
validWordAbbr.isUnique("cart"); // return true, no words in the dictionary have the abbreviation "c2t".
validWordAbbr.isUnique("cane"); // return false, dictionary word "cake" and word "cane" have the same abbreviation "c2e" but are not the same.
validWordAbbr.isUnique("make"); // return true, no words in the dictionary have the abbreviation "m2e".
validWordAbbr.isUnique("cake"); // return true, because "cake" is already in the dictionary and no other word in the dictionary has "c2e" abbreviation.
Constraints:
1 <= dictionary.length <= 3 * 1041 <= dictionary[i].length <= 20dictionary[i] consists of lowercase English letters.1 <= word.length <= 20word consists of lowercase English letters.5000 calls will be made to isUnique.Problem Overview: Design a structure that checks whether a word's abbreviation is unique in a dictionary. The abbreviation format is first letter + number of skipped characters + last letter. Words of length ≤ 2 keep their original form. The task is to preprocess a dictionary and quickly answer isUnique(word) queries.
Approach 1: Hash Map with Abbreviation to Word Set (O(n) build, O(1) query time, O(n) space)
Generate the abbreviation for every word in the dictionary and store it in a hash map where the key is the abbreviation and the value is a set of original words producing it. When you check a query word, compute its abbreviation and look it up with a constant-time hash lookup. The abbreviation is considered unique if the map entry either does not exist or contains only that exact word. This approach is easy to reason about and works well using a hash table for fast lookups while processing words stored in an array.
Approach 2: Optimized Hash Map with Single Representative (O(n) build, O(1) query time, O(n) space)
Instead of storing a full set of words, map each abbreviation to a single representative word. While building the structure, if the same abbreviation appears with a different word, store a special marker such as an empty string. During isUnique, compute the abbreviation and check the map. The abbreviation is unique if it does not exist in the map or if the stored value equals the query word. If the stored value is the marker, multiple different words share that abbreviation so the query is not unique. This reduces memory overhead compared to storing sets while still relying on fast string manipulation and hash lookups.
Recommended for interviews: The optimized hash map approach is what interviewers typically expect. It shows you understand how to compress state while maintaining O(1) lookups. Starting with the set-based version demonstrates correctness and clarity, then refining it to a single-value map shows strong problem-solving and design thinking.
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).
Python
Java
C++
Go
TypeScript
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Hash Map with Abbreviation to Word Set | O(n) build, O(1) query | O(n) | When prioritizing clarity and correctness; easy to implement and debug |
| Optimized Hash Map with Single Word | O(n) build, O(1) query | O(n) | Preferred interview solution; reduces memory while keeping constant-time lookups |
Leetcode 288. Unique Word Abbreviation in Python | Python Leetcode | Python Coding Tutorial | ASMR • Code is Art • 575 views views
Watch 5 more video solutions →Practice Unique Word Abbreviation with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor