Unique Word Abbreviation - Python Solution

1. Introduction

The "Unique Word Abbreviation" problem is a creative challenge that combines hash mapping and string processing. It involves creating a system to determine if a word's abbreviation is unique within a set of words. This problem has practical applications in text processing, such as in creating indexing systems or shorthand notations.

Problem

Design a system to abbreviate a word in such a way that its abbreviation is unique among a set of words. The abbreviation of a word is a concatenation of its first character, the number of characters between the first and last character, and its last character. The system should be able to check if a word's abbreviation is unique in the set.

2. Solution Steps

1. Initialize a hash map to store the abbreviations and their corresponding words.

2. Define a function to generate the abbreviation of a word.

3. While adding words to the system, generate their abbreviations and store them in the hash map.

4. Implement a function to check if an abbreviation is unique.

5. The abbreviation is unique if it's not in the hash map or if the corresponding word is the same as the word being checked.

3. Code Program

class ValidWordAbbr:
    def __init__(self, dictionary):
        self.abbr_dict = {}
        for word in dictionary:
            abbr = self.abbreviate(word)
            if abbr not in self.abbr_dict:
                self.abbr_dict[abbr] = word
            else:
                self.abbr_dict[abbr] = ""

    def abbreviate(self, word):
        if len(word) <= 2:
            return word
        return word[0] + str(len(word) - 2) + word[-1]

    def isUnique(self, word):
        abbr = self.abbreviate(word)
        return abbr not in self.abbr_dict or self.abbr_dict[abbr] == word

# Example Usage
vwa = ValidWordAbbr(["deer", "door", "cake", "card"])
print(vwa.isUnique("dear"))  # Output: False
print(vwa.isUnique("cart"))  # Output: True
print(vwa.isUnique("cane"))  # Output: False
print(vwa.isUnique("make"))  # Output: True

Output:

False
True
False
True

Explanation:

1. Abbreviation Generation: A function is used to create a standardized abbreviation for each word.

2. Hash Map Storing: Abbreviations are stored in a hash map with their respective words.

3. Uniqueness Check: The system checks if an abbreviation exists and if it corresponds to the same word.

4. Handling Edge Cases: Considers words with fewer than three characters.

5. Time Complexity: Efficiently handles queries with O(1) time complexity for lookup.

6. Practical Use: Demonstrates an approach for creating and managing unique identifiers or shorthand notations.


Comments