Skip to main content
Talentd

Unique Word Abbreviation - Solution & Explanation

MediumPremiumFree on FleetCodeArrayHash TableStringDesign12 min readAsked at: Google
Practice this problem

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 --> 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):
    • There is no word in dictionary whose abbreviation is equal to word's abbreviation.
    • For any word in 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 * 104
  • 1 <= dictionary[i].length <= 20
  • dictionary[i] consists of lowercase English letters.
  • 1 <= word.length <= 20
  • word consists of lowercase English letters.
  • At most 5000 calls will be made to isUnique.

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.

Solution

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).

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Hash Map with Abbreviation to Word SetO(n) build, O(1) queryO(n)When prioritizing clarity and correctness; easy to implement and debug
Optimized Hash Map with Single WordO(n) build, O(1) queryO(n)Preferred interview solution; reduces memory while keeping constant-time lookups

Video Solution

288. Unique Word Abbreviation (LeetCode) • hakunamatasq • 535 views views

Watch 4 more video solutions →

Frequently Asked Questions

Is Unique Word Abbreviation easy or hard?
Unique Word Abbreviation is generally considered a medium difficulty problem. The core idea is straightforward with hash maps, but handling duplicate abbreviations and designing the data structure correctly makes it slightly tricky.
How to solve Unique Word Abbreviation in O(n)?
Compute the abbreviation for each dictionary word and store it in a hash map. Map the abbreviation to either the word itself or a marker indicating multiple words share that abbreviation. Each query computes the abbreviation and performs a constant-time hash lookup to verify uniqueness.
What is the best approach for Unique Word Abbreviation?
The best approach uses a hash map that maps each abbreviation to a representative dictionary word. If another different word produces the same abbreviation, the entry is marked as non-unique. This allows O(n) preprocessing and O(1) time for each isUnique query.
What data structure is used in Unique Word Abbreviation?
A hash table is the core data structure. It maps abbreviations to dictionary words or markers indicating collisions. Efficient string processing is also required to generate abbreviations like first letter + skipped count + last letter.
What is the time complexity of Unique Word Abbreviation?
Building the data structure requires O(n) time where n is the number of dictionary words. Each isUnique lookup runs in O(1) average time using a hash table. Space complexity is O(n) to store abbreviations and their associated words.
Unique Word Abbreviation Python or Java solution approach?
Both Python and Java implementations follow the same idea: compute abbreviations and store them in a hash map. Python typically uses a dictionary, while Java uses HashMap<String, String>. The lookup logic checks whether the stored value matches the query word or indicates a collision.
Is Unique Word Abbreviation asked at Google, Amazon, or Meta?
Unique Word Abbreviation is a common design-style interview problem that appears in coding rounds at companies like Google and Amazon. It tests hash table usage, string manipulation, and the ability to design efficient lookup structures.

Ready to solve this problem?

Practice Unique Word Abbreviation with our built-in code editor and test cases.

Practice on FleetCode
Previous

Generalized Abbreviation

Next

Two Sum III - Data structure design