NUHMAN.com

Introduction

LeetCode 288: Unique Word Abbreviation asks you to design a data structure that supports two operations for handling words and their abbreviations:

1. Word Abbreviation: An abbreviation of a word replaces inner letters with their count. For example, "word" could be abbreviated as "w2d" (replacing "or" with "2").
2. Uniqueness Check: Given a word, you need to check if its abbreviation is unique among a list of words.

The problem tests your understanding of string manipulation and how to handle abbreviations effectively using efficient data structures like hashmaps.

Problem Statement

Implement a class ValidWordAbbr that supports two operations:

1. isUnique(word: str) -> bool: Returns true if the abbreviation of word is unique among the stored words.
2. addWord(word: str) -> None: Adds a word to the dictionary of words.

An abbreviation for a word follows the rules:

• It replaces consecutive inner characters of a word with a number indicating how many characters are omitted.
• For example, "word" → "w2d" where "2" is the abbreviation for the two characters "or".

A word has a unique abbreviation if no other word can be abbreviated to the same form.

Example

python

Input:
["ValidWordAbbr", "isUnique", "addWord", "isUnique", "addWord", "isUnique"]
[[], ["hello"], ["hello"], ["hello"], ["hell"], ["hell"]]

Output:
[null, true, null, false, null, true]

Explanation:
1. ValidWordAbbr validWordAbbr = new ValidWordAbbr();
2. validWordAbbr.isUnique("hello") returns true.
3. validWordAbbr.addWord("hello") adds the word "hello" to the dictionary.
4. validWordAbbr.isUnique("hello") returns false because "hello" already exists.
5. validWordAbbr.addWord("hell") adds the word "hell" to the dictionary.
6. validWordAbbr.isUnique("hell") returns true because "hell" has a unique abbreviation.

✅ Step-by-Step Solution

🧠 Intuition

1. Abbreviation Rules:

• The abbreviation of a word is formed by keeping the first letter, followed by the number of characters in the middle, and then the last letter.
• For example, "hello" → "h3o", and "hell" → "h2l".

1. Data Structure Choice:

• Use a hashmap to store the words and their corresponding abbreviations.
• Each word will map to its abbreviation, and we need to check if an abbreviation is already taken by any other word.

1. Handling Uniqueness:

• For each word, compute its abbreviation and store it.
• If the abbreviation is already taken by another word, mark the abbreviation as non-unique.

1. Efficient Computation:

• For each word, generate its abbreviation and compare it with others in the dictionary to check uniqueness.

✅ Approach

Operations

1. addWord(word: str) -> None:

• Compute the abbreviation for the given word.
• Store the word and its abbreviation in the dictionary.

1. isUnique(word: str) -> bool:

• Compute the abbreviation for the given word.
• Check if the abbreviation is unique by comparing it with other words in the dictionary.

✅ Python Code

python

class ValidWordAbbr:
    def __init__(self):
        self.words = {}
        
    def _get_abbreviation(self, word: str) -> str:
        if len(word) <= 3:
            return word  # Words of length 3 or less have no abbreviation.
        return word[0] + str(len(word) - 2) + word[-1]

    def addWord(self, word: str) -> None:
        abbr = self._get_abbreviation(word)
        if abbr not in self.words:
            self.words[abbr] = {word}
        else:
            self.words[abbr].add(word)
    
    def isUnique(self, word: str) -> bool:
        abbr = self._get_abbreviation(word)
        if abbr not in self.words:
            return True
        # Check if the abbreviation is only associated with the given word.
        return len(self.words[abbr]) == 1 and word in self.words[abbr]

🧪 How It Works

1. _get_abbreviation(word): A helper function computes the abbreviation for a word. If the word length is 3 or fewer, it returns the word as is because abbreviations are only applicable for longer words.
2. addWord(word):

• Compute the abbreviation for the word.
• Add the word to a set associated with its abbreviation in the words dictionary.

1. isUnique(word):

• Compute the abbreviation for the word.
• Check if the abbreviation exists in the dictionary and if the word is the only one associated with that abbreviation.

⏱️ Time and Space Complexity

MetricValueTime ComplexityO(k), where k is the length of the word for addWord and isUnique (since we are generating the abbreviation and checking the dictionary)Space ComplexityO(m * k), where m is the number of words stored and k is the average length of a word

• The time complexity for both operations is linear with respect to the length of the word, as we need to compute its abbreviation and possibly check the dictionary.
• The space complexity depends on the number of words and their length, since each word and its abbreviation are stored in the dictionary.

🔍 Edge Cases

1. Short Words (<= 3 characters): These are not abbreviated, so they should be treated as unique unless exactly the same word exists.
2. Multiple Words with Same Abbreviation: Words like "hello" and "hell" may have the same abbreviation ("h3o" and "h2l"), but they are distinct words.
3. Abbreviations with Multiple Words: If two different words share the same abbreviation, then the abbreviation is no longer unique.

✅ Conclusion

LeetCode 288: Unique Word Abbreviation is an interesting problem that involves string manipulation and dictionary management. The solution uses a hashmap to track abbreviations and efficiently checks for uniqueness.

This problem is useful for practicing abbreviations, hashmap-based lookups, and efficiently managing collections of words. It can also be extended to solve similar problems involving word filtering or encoding strategies.