LeetCode 288: Unique Word Abbreviation Solution in Python – A Step-by-Step Guide

What Is LeetCode 288: Unique Word Abbreviation?

In LeetCode 288: Unique Word Abbreviation, you’re tasked with creating a ValidWordAbbr class. It takes a dictionary of words at initialization, and then you use its isUnique(word) method to check if a given word’s abbreviation is unique—meaning no other word in the dictionary has the same abbreviation. The abbreviation rule is: take the first letter, the number of letters between the first and last, and the last letter (e.g., "dog" → "d1g", "internationalization" → "i18n"). For example, with a dictionary ["deer", "door"], "deer" (d2r) isn’t unique because "door" shares "d2r." This problem tests your ability to organize and compare data, sharing a vibe with hash-based challenges like LeetCode 49: Group Anagrams.

Problem Statement

• Input: A list of strings dictionary for initialization; a string word for isUnique.
• Output: A class with:
• __init__(dictionary): Sets up the dictionary.
• isUnique(word): Returns True if word’s abbreviation is unique, False otherwise.
• Rules: Abbreviation is first letter + middle length + last letter; unique means no other dictionary word shares it.

Constraints

• dictionary length: 0 to 10⁵ (100,000).
• Word length: 1 to 20.
• Words contain only lowercase English letters.

Examples

• Input: dictionary = ["deer", "door", "cake", "card"]
• isUnique("deer") → False (d2r shared with "door")
• isUnique("cake") → True (c3e unique)
• isUnique("cane") → True (c3e unique, not in dictionary)
• Input: dictionary = ["hello"]
• isUnique("hello") → True (h3o unique)
• Input: dictionary = []
• isUnique("word") → True (w2d unique, empty dictionary)

Understanding the Problem: Checking the Shorthand

To solve LeetCode 288: Unique Word Abbreviation in Python, we need to create a class that: 1. Takes a list of words and preps them for checking. 2. For any word, figures out its abbreviation and checks if it’s unique in the dictionary.

The abbreviation is simple: for "dog," it’s "d" (first), "1" (middle length: 3-2=1), "g" (last) → "d1g." The trick is checking uniqueness without redoing work every time. We’ll use:

• Best Solution (Hash Map): O(n) init, O(1) per check—fast and clever.
• Alternative Solution (Brute-Force): O(n) per check—easy but slow.

Let’s dive into the hash map solution with a beginner-friendly explanation.

Best Solution: Hash Map with Abbreviation Tracking

Why This Is the Best Solution

The hash map approach is the best for LeetCode 288 because it’s super efficient: O(n) time to set up (where n is dictionary length) and O(1) time for each isUnique check. It uses a dictionary (hash map) to store abbreviations and their words, so we can quickly see if an abbreviation is shared. For beginners, it’s like making a cheat sheet upfront—then checking it takes no time at all!

How It Works—Explained for Beginners

Let’s break this down like we’re organizing a notebook:

• Step 1: Make a Shortcut Maker:
• Create a little helper that turns any word into its abbreviation. For "cat," it’s:
• First letter: "c."
• Middle length: 3 letters total, skip first and last, so 1 → "1."
• Last letter: "t."
• Result: "c1t."
• Step 2: Build the Notebook (Hash Map):
• When the class starts, go through each dictionary word (e.g., "deer," "door").
• Get their abbreviations ("d2r," "d2r").
• Write them in a notebook (hash map) where the abbreviation is the label, and the value is a list of words with that label—like "d2r: [deer, door]."
• Step 3: Check Uniqueness:
• For a word like "deer," get its abbreviation ("d2r").
• Look it up in the notebook:
• If "d2r" isn’t there, it’s unique—great!
• If it’s there with just "deer," still unique.
• If it’s there with "deer" and "door," not unique—too many matches!
• Step 4: Why It Works:
• The hash map stores everything once at the start, so checking is fast.
• It catches duplicates by seeing if an abbreviation has multiple words.

It’s like labeling jars in your pantry—once they’re labeled, finding duplicates is a breeze!

Step-by-Step Example

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

• Init:
• "deer" → "d2r" → {"d2r": ["deer"]}.
• "door" → "d2r" → {"d2r": ["deer", "door"]}.
• "cake" → "c3e" → {"d2r": ["deer", "door"], "c3e": ["cake"]}.
• "card" → "c2d" → {"d2r": ["deer", "door"], "c3e": ["cake"], "c2d": ["card"]}.
• isUnique("deer"):
• Abbr = "d2r."
• Look up "d2r": ["deer", "door"]—two words, not unique → False.
• isUnique("cake"):
• Abbr = "c3e."
• Look up "c3e": ["cake"]—one word, unique → True.
• isUnique("cane"):
• Abbr = "c3e."
• Look up "c3e": ["cake"]—one word, not "cane," unique → True.

Code with Detailed Line-by-Line Explanation

Here’s the Python code, explained so any beginner can follow:

Copy codeclass ValidWordAbbr:
    def __init__(self, dictionary: List[str]):
        # Step 1: Create a notebook (hash map) to store abbreviations
        self.abbr_map = {}

        # Step 2: Helper to make abbreviations
        def get_abbr(word):
            if len(word) <= 2:
                return word  # Too short, use as-is
            return word[0] + str(len(word) - 2) + word[-1]  # First + count + last

        # Step 3: Fill the notebook with dictionary words
        for word in dictionary:
            abbr = get_abbr(word)
            if abbr not in self.abbr_map:
                self.abbr_map[abbr] = []  # New label, empty list
            self.abbr_map[abbr].append(word)  # Add word to label’s list

    def isUnique(self, word: str) -> bool:
        # Step 4: Check if word’s abbreviation is unique
        def get_abbr(word):
            if len(word) <= 2:
                return word
            return word[0] + str(len(word) - 2) + word[-1]

        abbr = get_abbr(word)  # Get the word’s shorthand
        if abbr not in self.abbr_map:
            return True  # Not in notebook—unique!
        words = self.abbr_map[abbr]  # List of words with this abbr
        return len(words) == 1 and words[0] == word  # Only one, and it’s this word?

• Line 4-5: Set up an empty hash map (our notebook) to hold abbreviations and words.
• Line 7-10: Helper function get_abbr:
• If word is 2 letters or less (e.g., "to"), return it (no middle to count).
• Else, take first letter, count middle letters (total length - 2), add last letter.
• Line 12-16: In __init__:
• For each word, get its abbreviation.
• If abbr isn’t in the map, start a new list; add the word to that abbr’s list.
• Line 18-26: In isUnique:
• Same helper makes the word’s abbr.
• If abbr isn’t in the map, it’s unique—return True.
• Get the list of words with that abbr; it’s unique if the list has just this word.

• Time Complexity: O(n) for init (n = dictionary length), O(1) per isUnique—fast lookups!
• Space Complexity: O(n)—stores dictionary words in the hash map.

This is like a quick-reference guide—set it up once, check anytime!

Alternative Solution: Brute-Force Checking

Why an Alternative Approach?

The brute-force method checks each dictionary word’s abbreviation against the target word’s every time—O(n) per check. It’s slower but super simple, like comparing every label by hand. Great for beginners to see the basics before the hash map magic!

How It Works—Explained for Beginners

Let’s think of this as a manual check:

• Step 1: Store the Dictionary:
• Keep the list of words as-is when the class starts.
• Step 2: Make Abbreviations:
• Same helper: "dog" → "d1g."
• Step 3: Check Each Word:
• For a word like "deer," get "d2r."
• Look at every dictionary word’s abbreviation:
• If it matches "d2r" and isn’t "deer," not unique.
• If no matches (or only "deer"), unique.
• Step 4: Why It Works:
• It checks everything fresh each time—slow but sure.

It’s like flipping through a book page-by-page to find a match!

Step-by-Step Example

Example: dictionary = ["deer", "door"]

• Init: Store ["deer", "door"].
• isUnique("deer"):
• Abbr = "d2r."
• "deer" → "d2r" (skip, same word).
• "door" → "d2r"—match, not "deer" → False.
• isUnique("dog"):
• Abbr = "d1g."
• "deer" → "d2r"—no match.
• "door" → "d2r"—no match.
• No matches → True.

Code for Brute-Force Approach

Copy codeclass ValidWordAbbr:
    def __init__(self, dictionary: List[str]):
        self.dictionary = dictionary

    def isUnique(self, word: str) -> bool:
        def get_abbr(w):
            if len(w) <= 2:
                return w
            return w[0] + str(len(w) - 2) + w[-1]

        abbr = get_abbr(word)
        for dict_word in self.dictionary:
            if dict_word != word and get_abbr(dict_word) == abbr:
                return False
        return True

• Time Complexity: O(n) per isUnique—checks every word.
• Space Complexity: O(n)—stores dictionary.

It’s a slow but steady check!

Comparing the Two Solutions

• Hash Map (Best):
• Pros: O(n) init, O(1) check, fast lookups.
• Cons: Takes setup time.
• Brute-Force (Alternative):
• Pros: O(1) init, simple logic.
• Cons: O(n) per check, slow.

Hash map wins for speed.

Additional Examples and Edge Cases

• ["a"]: isUnique("a") → True.
• ["to", "to"]: isUnique("to") → False.
• []: isUnique("any") → True.

Both handle these well.

Complexity Breakdown

• Hash Map: Init O(n), Check O(1), Space O(n).
• Brute-Force: Init O(1), Check O(n), Space O(n).

Hash map is the champ.

Key Takeaways

• Hash Map: Pre-organize for speed—awesome!
• Brute-Force: Check everything—easy start!
• Dictionaries: Key-value power.
• Python Tip: Lists and maps rock—see [Python Basics](/python/basics).

Final Thoughts: Shorten and Shine

LeetCode 288: Unique Word Abbreviation in Python is a neat word puzzle. The hash map solution zips through checks, while brute-force offers a gentle intro. Want more? Try LeetCode 49: Group Anagrams or LeetCode 205: Isomorphic Strings. Ready to abbreviate? Head to Solve LeetCode 288 on LeetCode and spot those uniques today!