LeetCode 288: Unique Word Abbreviation

Problem Restatement

We are given a dictionary of words.

We need to design a class that can answer this query:

isUnique(word)

It returns whether word has a unique abbreviation in the dictionary.

The abbreviation rule is:

If the word length is less than 3, the abbreviation is the word itself.

Otherwise:

first letter + number of middle letters + last letter

For example:

"dog" -> "d1g"
"internationalization" -> "i18n"
"it" -> "it"

A word is unique if either:

1. No dictionary word has the same abbreviation.
2. The only dictionary words with that abbreviation are exactly the same as word.

The source constraints include dictionary size up to 3 * 10^4, word length up to 20, and at most 5000 calls to isUnique.

Input and Output

Class shape:

class ValidWordAbbr:
    def __init__(self, dictionary: list[str]):
        ...

    def isUnique(self, word: str) -> bool:
        ...

Examples

For:

dictionary = ["deer", "door", "cake", "card"]

The abbreviations are:

Now:

isUnique("dear") -> False

because:

"dear" -> "d2r"

and "deer" and "door" already have abbreviation "d2r".

isUnique("cart") -> True

because:

"cart" -> "c2t"

and no dictionary word has abbreviation "c2t".

isUnique("cane") -> False

because:

"cane" -> "c2e"
"cake" -> "c2e"

They are different words with the same abbreviation.

isUnique("make") -> True

because no dictionary word has abbreviation "m2e".

First Thought: Scan the Dictionary Every Time

A direct solution stores the dictionary as a list.

For every isUnique(word) query:

1. Compute the abbreviation of word.
2. Scan every dictionary word.
3. If another word has the same abbreviation, return False.
4. Otherwise return True.

Code:

class ValidWordAbbr:
    def __init__(self, dictionary: list[str]):
        self.dictionary = dictionary

    def isUnique(self, word: str) -> bool:
        target = self.abbr(word)

        for other in self.dictionary:
            if other != word and self.abbr(other) == target:
                return False

        return True

    def abbr(self, word: str) -> str:
        if len(word) < 3:
            return word

        return word[0] + str(len(word) - 2) + word[-1]

This is correct, but each query scans the whole dictionary.

With many calls to isUnique, this repeats the same abbreviation work again and again.

Key Insight

Precompute a hash map from abbreviation to the set of dictionary words that produce it.

Example:

dictionary = ["deer", "door", "cake", "card"]

Build:

{
    "d2r": {"deer", "door"},
    "c2e": {"cake"},
    "c2d": {"card"},
}

Then for a query word:

1. Compute its abbreviation.
2. Look up the set of dictionary words with that abbreviation.
3. The word is unique if:
   • the abbreviation does not exist, or
   • the set contains only that exact word.

This also handles duplicate dictionary entries.

For example:

dictionary = ["door", "door"]

The set for "d2r" is:

{"door"}

So:

isUnique("door") -> True

because there is no different dictionary word with the same abbreviation.

Algorithm

During initialization:

1. Create a hash map:

abbr_to_words = {}

2. For each word in the dictionary:
   • Compute its abbreviation.
   • Add the word to the set for that abbreviation.

For isUnique(word):

1. Compute key = abbr(word).
2. If key does not exist in the map, return True.
3. Otherwise, return True only if the set is exactly {word}.

Correctness

For each abbreviation, the hash map stores exactly the set of dictionary words that produce that abbreviation.

When isUnique(word) is called, any possible conflict must come from dictionary words stored under the same abbreviation as word.

If the abbreviation is absent from the map, no dictionary word has that abbreviation, so word is unique.

If the abbreviation exists and its set contains only word, then every dictionary word with that abbreviation is the same as word. So there is no other word from the dictionary with the same abbreviation.

If the set contains any word different from word, then another dictionary word shares the abbreviation, so word is not unique.

Therefore the algorithm returns exactly the required answer.

Complexity

Let:

N = number of words in dictionary
L = maximum word length

Since LeetCode word length is at most 20, isUnique is effectively constant time.

Implementation

from collections import defaultdict

class ValidWordAbbr:
    def __init__(self, dictionary: list[str]):
        self.abbr_to_words = defaultdict(set)

        for word in dictionary:
            key = self.abbr(word)
            self.abbr_to_words[key].add(word)

    def isUnique(self, word: str) -> bool:
        key = self.abbr(word)

        if key not in self.abbr_to_words:
            return True

        words = self.abbr_to_words[key]

        return len(words) == 1 and word in words

    def abbr(self, word: str) -> str:
        if len(word) < 3:
            return word

        return word[0] + str(len(word) - 2) + word[-1]

Code Explanation

We store abbreviation groups here:

self.abbr_to_words = defaultdict(set)

Each abbreviation maps to a set, not a list.

This matters because duplicate dictionary words should not create false conflicts.

For each dictionary word:

key = self.abbr(word)
self.abbr_to_words[key].add(word)

we compute its abbreviation and place it in the correct group.

For each query:

key = self.abbr(word)

we compute the abbreviation of the query word.

If the abbreviation was never seen:

if key not in self.abbr_to_words:
    return True

then the word is unique.

Otherwise, we inspect the group:

words = self.abbr_to_words[key]

The query is unique only when this group contains exactly one distinct word, and that word equals the query:

return len(words) == 1 and word in words

The abbreviation helper follows the problem rule:

if len(word) < 3:
    return word

Otherwise:

return word[0] + str(len(word) - 2) + word[-1]

Testing

def test_valid_word_abbr():
    v = ValidWordAbbr(["deer", "door", "cake", "card"])

    assert v.isUnique("dear") is False
    assert v.isUnique("cart") is True
    assert v.isUnique("cane") is False
    assert v.isUnique("make") is True

    v = ValidWordAbbr(["door", "door"])
    assert v.isUnique("door") is True
    assert v.isUnique("dear") is False

    v = ValidWordAbbr(["it", "is"])
    assert v.isUnique("it") is True
    assert v.isUnique("if") is True
    assert v.isUnique("is") is True

    print("all tests passed")

test_valid_word_abbr()

Test meaning: