Unique Word Abbreviation - Video Solutions
288. Unique Word Abbreviation (LeetCode)
Unique Word Abbreviation - Video Solution
Watch 5 video solutions for Unique Word Abbreviation, a medium level problem involving Array, Hash Table, String. This walkthrough by hakunamatasq has 535 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
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 --> d1gbecause there is one letter between the first letter'd'and the last letter'g'.internationalization --> i18nbecause there are 18 letters between the first letter'i'and the last letter'n'.it --> itbecause any word with only two characters is an abbreviation of itself.
Implement the ValidWordAbbr class:
ValidWordAbbr(String[] dictionary)Initializes the object with adictionaryof words.boolean isUnique(string word)Returnstrueif either of the following conditions are met (otherwise returnsfalse):- There is no word in
dictionarywhose abbreviation is equal toword's abbreviation. - For any word in
dictionarywhose abbreviation is equal toword's abbreviation, that word andwordare the same.
- There is no word in
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 <= 20wordconsists of lowercase English letters.- At most
5000calls will be made toisUnique.
Approach Overview
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.
Complexity Analysis
| 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 |