Watch 10 video solutions for Unique Word Abbreviation, a medium level problem involving Array, Hash Table, String. This walkthrough by Greg Hogg has 221,977 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |