Unique Word Abbreviation

The task is to create a class that can identify valid word abbreviations based on the given rules and constraints.

Approach

Preprocess the Dictionary: Build a mapping between the abbreviations and their corresponding words from the given dictionary. Store the words having the same abbreviation.
Check Abbreviation: For each given word, compute its abbreviation and check if there are any other words in the dictionary with the same abbreviation.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class ValidWordAbbr:
    def __init__(self, dictionary: List[str]):
        self.abbr_dict = defaultdict(set)

        # Create a mapping between abbreviations and words
        for word in dictionary:
            abbr = self.abbreviation(word)
            self.abbr_dict[abbr].add(word)

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

    def isUnique(self, word: str) -> bool:
        abbr = self.abbreviation(word)
        words_with_same_abbr = self.abbr_dict.get(abbr, set())
        return len(words_with_same_abbr) == 0 or (words_with_same_abbr == {word})

# Example usage:
# validWordAbbr = ValidWordAbbr(["deer", "door", "cake", "card"])
# validWordAbbr.isUnique("dear") # return false

Explanation

The abbreviation method computes the abbreviation of a given word based on the described rules.
The isUnique method checks if the abbreviation of a given word is unique in the dictionary or if the word itself exists in the dictionary.

Key Takeaways

The preprocessing step helps in efficiently checking the abbreviation for each word.
The time complexity for creating the abbreviation dictionary is (O(nm)), where (n) is the number of words and (m) is the average length of the words.
The time complexity for the isUnique method is (O(1)), as we perform a constant number of operations.
The space complexity is (O(n)), where (n) is the number of words in the dictionary.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
from collections import defaultdict
from typing import List

class ValidWordAbbr:
    def __init__(self, dictionary: List[str]):
        self.abbr_dict = defaultdict(set)
        for word in dictionary:
            abbreviation = self.get_abbreviation(word)
            self.abbr_dict[abbreviation].add(word)

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

    def isUnique(self, word: str) -> bool:
        abbreviation = self.get_abbreviation(word)
        words_with_abbr = self.abbr_dict[abbreviation]

        if len(words_with_abbr) == 0:
            return True
        if len(words_with_abbr) == 1 and word in words_with_abbr:
            return True

        return False