288. Unique Word Abbreviation

MediumDesignArrayHash TableString
Leetcode Link

Problem Description

The problem involves creating a class called ValidWordAbbr that can store a dictionary of words and check if a given word's abbreviation is unique within that dictionary. An abbreviation of a word consists of its first letter, the number of characters between the first and last letter, and its last letter. If a word is only two characters long, the abbreviation is the word itself.

To clarify:

  • The abbreviation for "dog" is "d1g".
  • The abbreviation for "internationalization" is "i18n".
  • The abbreviation for "it" is "it" itself.

The ValidWordAbbr class should support the following operations:

  • Initialization (__init__): When an instance of ValidWordAbbr is created, it is initialized with a given list of words, which is referred to as the dictionary.

  • Check Uniqueness (isUnique): This method checks whether a word's abbreviation is unique. A word's abbreviation is considered unique if no other word in the dictionary has the same abbreviation or if the only word in the dictionary with the same abbreviation is the word itself.

Intuition

To solve the problem efficiently, we can use a dictionary (a hash map) to store abbreviations of the words in the given dictionary with their corresponding words.

Here's the thought process to arrive at the solution:

  • Storing Abbreviations: We need a way to conveniently check if the abbreviation of a given word is unique among the stored words. Therefore, we can store the abbreviations in a way that allows us to quickly lookup which words share the same abbreviation.

  • Using Sets for Words: For each abbreviation, we might have multiple words corresponding to it in the dictionary. We use a set to store these words to avoid duplicates and enable fast existence checks.

  • Checking Uniqueness: When checking the uniqueness of the abbreviation of a given word, there are two conditions to consider:

    1. The abbreviation does not exist in our stored abbreviations. This guarantees uniqueness.
    2. The abbreviation exists, but it is linked exclusively to the given word.
  • Edge Cases: We don't need to store abbreviations for words of length two or less since they are abbreviations of themselves and cannot conflict with others.

Implementing the above logic results in the provided solution, where:

  • The __init__ function creates a hash table to store the words with their abbreviations as keys.
  • The word_abbr helper function generates the abbreviation for any given string.
  • The isUnique function uses word_abbr to check the conditions that classify the abbreviation as unique.
Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece:

Which of the tree traversal order can be used to obtain elements in a binary search tree in sorted order?

Solution Approach

The solution makes use of a hash table and sets to efficiently store and query word abbreviations.

  • Initializing the Object:

    • A defaultdict of sets is used to store the words against their abbreviations. defaultdict is a subclass of dict which provides a default value for a key that does not exist.
    • Upon initialization (__init__ method), the dictionary takes each word and computes its abbreviation using a helper function (word_abbr).
    • The abbreviated form of the word is used as a key, and the word itself is added to the set corresponding to that key.
  • Abbreviating the Word:

    • The helper function word_abbr creates an abbreviation by taking the first and last character of the word and the count of the characters in between.
    • The abbreviation is formed as first_char + (len(word) - 2) + last_char.
    • If the word is shorter than 3 characters, the word itself is returned as its abbreviation.
  • Checking Uniqueness:

    • isUnique checks if a given word's abbreviated form is unique in the dictionary.
    • First, it computes the abbreviation of the word to be checked.
    • Then it retrieves the set of words that share the same abbreviation from our hash table.
    • If this set is empty, no words in our dictionary have the same abbreviation, and it returns True.
    • If the set contains only the given word, this again ensures uniqueness, and it returns True.
    • The check len(words) == 1 and word in words ensures that the word's set contains exactly one word and that the word is the one we are checking.
    • Otherwise, the word is not unique, and it returns False.

Here is how the core part of the implementation connects to the solution approach:

1class ValidWordAbbr:
2    def __init__(self, dictionary: List[str]):
3        self.words = defaultdict(set)
4        for word in dictionary:
5            abbr = self.word_abbr(word)       # Compute the abbreviation
6            self.words[abbr].add(word)        # Map it with the word in set
7
8    def isUnique(self, word: str) -> bool:
9        abbr = self.word_abbr(word)           # Abbreviation for the word
10        words = self.words[abbr]              # Get the set of words with same abbreviation
11        return not words or (len(words) == 1 and word in words) # Check for uniqueness
12
13    def word_abbr(self, s):
14        return s if len(s) < 3 else f'{s[0]}{len(s) - 2}{s[-1]}' # Helper function

By using a hash table and sets, the solution efficiently supports both the addition of words to the dictionary and the uniqueness check, optimizing for quick lookups and taking advantage of the fact that sets offer constant time complexity for insertion and lookup operations.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

The three-steps of Depth First Search are:

  1. Identify states;
  2. Draw the state-space tree;
  3. DFS on the state-space tree.

Example Walkthrough

We'll illustrate how the ValidWordAbbr class operates using a small example. Let's say we want to initialize our dictionary with the words ["deer", "door", "cake", "card"]. We'll then check the uniqueness of certain abbreviations.

Initialization

When we create an instance of ValidWordAbbr with our dictionary, it will process each word and store its abbreviation:

  • "deer" -> "d2r"
  • "door" -> "d2r"
  • "cake" -> "c2e"
  • "card" -> "c2d"

Our hash table for storing abbreviations and corresponding words will look like this:

1{
2  "d2r": {"deer", "door"}, // Both "deer" and "door" abbreviate to "d2r"
3  "c2e": {"cake"},         // "cake" abbreviates to "c2e"
4  "c2d": {"card"}          // "card" abbreviates to "c2d"
5}

Checking Uniqueness

Let's check the uniqueness of the word "dear":

  1. Calculate its abbreviation: "dear" -> "d2r"
  2. Check if "d2r" is in our hash table. It is, and its value is the set {"door", "deer"}.
  3. Since "dear" is not in this set and the set contains more than one element, "d2r" is not unique to "dear".
  4. Therefore, isUnique("dear") returns False.

Now, let's check the uniqueness of the word "cart":

  1. Calculate its abbreviation: "cart" -> "c2t"
  2. Check if "c2t" is in our hash table. It isn't.
  3. Since there are no words in our dictionary that abbreviate to "c2t", the abbreviation is unique.
  4. Thus, isUnique("cart") returns True.

Lastly, let's check the uniqueness of the word "cake":

  1. Calculate its abbreviation: "cake" -> "c2e"
  2. Look up "c2e" in our hash table. We find the set {"cake"}.
  3. Since "cake" is in this set and it is the only element, its abbreviation is unique to "cake".
  4. Hence, isUnique("cake") returns True.

This example demonstrates how ValidWordAbbr uses a hash table and sets to efficiently store word abbreviations and determine the uniqueness of a word's abbreviation within the dictionary.

Not Sure What to Study? Take the 2-min Quiz:

A heap is a ...?

Python Solution

1from collections import defaultdict
2
3class ValidWordAbbr:
4    def __init__(self, dictionary: list[str]):
5        # Initialize a dictionary to keep track of the abbreviations.
6        self.word_to_abbr = defaultdict(set)
7        # Populating the self.word_to_abbr with the word abbreviations.
8        for word in dictionary:
9            abbr = self._get_word_abbr(word)
10            self.word_to_abbr[abbr].add(word)
11
12    def isUnique(self, word: str) -> bool:
13        # Check if the given word has a unique abbreviation in the dictionary.
14        abbr = self._get_word_abbr(word)
15        words_with_abbr = self.word_to_abbr[abbr]
16        # A word is unique if it's the only word with that abbreviation
17        # or if the abbreviation isn't in the dictionary at all.
18        return not words_with_abbr or (len(words_with_abbr) == 1 and word in words_with_abbr)
19
20    def _get_word_abbr(self, word: str) -> str:
21        # Helper method to generate the abbreviation of a word.
22        if len(word) < 3:
23            # If the word is less than 3 characters, its abbreviation is the word itself.
24            return word
25        else:
26            # For words with length 3 or more, abbreviation is first letter, number of chars between, last letter.
27            return f'{word[0]}{len(word) - 2}{word[-1]}'
28
29# Example on how to use the class:
30# obj = ValidWordAbbr(["hello", "world"])
31# unique_status = obj.isUnique("hello")
32

Java Solution

1import java.util.HashMap;
2import java.util.HashSet;
3import java.util.Map;
4import java.util.Set;
5
6class ValidWordAbbr {
7
8    // Map to hold the abbreviated word as the key and the set of original words as the value
9    private Map<String, Set<String>> abbreviationMap;
10
11    // Constructor which initializes the map and processes the input dictionary
12    public ValidWordAbbr(String[] dictionary) {
13        abbreviationMap = new HashMap<>();
14        for (String word : dictionary) {
15            // Create abbreviation for the current word
16            String abbreviation = createAbbreviation(word);
17            // If abbreviation is already in the map, add the original word to the set
18            // Otherwise, create a new set and add the word
19            abbreviationMap.computeIfAbsent(abbreviation, k -> new HashSet<>()).add(word);
20        }
21    }
22
23    // Function to check if a given word's abbreviation is unique in the dictionary
24    public boolean isUnique(String word) {
25        // Get the abbreviation for the given word
26        String abbreviation = createAbbreviation(word);
27        // Retrieve the set of words that have the same abbreviation
28        Set<String> wordsWithSameAbbreviation = abbreviationMap.get(abbreviation);
29        // The word's abbreviation is unique if:
30        // 1) No other words have the same abbreviation (set is null), or
31        // 2) Only one word has the same abbreviation and it is the word itself
32        return wordsWithSameAbbreviation == null || 
33               (wordsWithSameAbbreviation.size() == 1 && wordsWithSameAbbreviation.contains(word));
34    }
35
36    // Helper method to generate the abbreviation for a given word
37    private String createAbbreviation(String word) {
38        int wordLength = word.length();
39        // If word is less than 3 characters long, abbreviation is the word itself
40        if (wordLength < 3) {
41            return word;
42        }
43        // Otherwise, abbreviation format: first letter + number of chars between + last letter
44        return word.charAt(0) + Integer.toString(wordLength - 2) + word.charAt(wordLength - 1);
45    }
46}
47
48/*
49 * Example of how to use the class:
50 * ValidWordAbbr obj = new ValidWordAbbr(dictionary);
51 * boolean isWordUnique = obj.isUnique(word);
52 */
53

C++ Solution

1#include <vector>
2#include <string>
3#include <unordered_map>
4#include <unordered_set>
5
6class ValidWordAbbr {
7public:
8    // Using an unordered_map to map abbreviations to a set of original words
9    std::unordered_map<std::string, std::unordered_set<std::string>> abbrToWordsMap;
10
11    // Constructor that accepts a dictionary and builds the abbreviation map
12    ValidWordAbbr(std::vector<std::string>& dictionary) {
13        for (const auto& word : dictionary) {
14            std::string abbr = getAbbreviation(word);
15            abbrToWordsMap[abbr].insert(word);
16        }
17    }
18
19    // Checks if a word with a given abbreviation is unique within the dictionary
20    bool isUnique(std::string word) {
21        std::string abbr = getAbbreviation(word);
22        if (abbrToWordsMap.find(abbr) == abbrToWordsMap.end()) {
23            // If abbreviation isn't in the map, the word is considered unique
24            return true;
25        }
26      
27        const auto& wordsWithSameAbbr = abbrToWordsMap[abbr];
28        // A word is unique if it is the only word with its abbreviation
29        // or it's the only instance of that word with its abbreviation
30        return wordsWithSameAbbr.size() == 1 && wordsWithSameAbbr.count(word) > 0;
31    }
32
33private:
34    // Helper method to calculate an abbreviation for a word
35    std::string getAbbreviation(const std::string& word) {
36        size_t n = word.length();
37        if (n < 3) {
38            // Words of length less than 3 are their own abbreviation
39            return word;
40        }
41        // Abbreviations are created by taking the first letter, the count of 
42        // the number of characters in between, and the last letter
43        return word.front() + std::to_string(n - 2) + word.back();
44    }
45};
46
47/**
48 * Your ValidWordAbbr object will be instantiated and called as such:
49 * ValidWordAbbr* obj = new ValidWordAbbr(dictionary);
50 * bool param_1 = obj->isUnique(word);
51 */
52

Typescript Solution

1// A map to store abbreviations (keys) and the set of original words (values)
2const abbrToWordsMap: { [abbr: string]: Set<string> } = {};
3
4/**
5 * Builds the abbreviation map for the given dictionary.
6 * @param dictionary An array of words to initialize the abbreviation map.
7 */
8function initializeValidWordAbbr(dictionary: string[]): void {
9    dictionary.forEach(word => {
10        let abbr = getAbbreviation(word);
11        if (!abbrToWordsMap[abbr]) {
12            abbrToWordsMap[abbr] = new Set<string>();
13        }
14        abbrToWordsMap[abbr].add(word);
15    });
16}
17
18/**
19 * Checks if a word with a given abbreviation is unique within the dictionary.
20 * @param word The word to check for uniqueness.
21 * @returns True if the word's abbreviation is unique, false otherwise.
22 */
23function isUnique(word: string): boolean {
24    let abbr = getAbbreviation(word);
25    let wordsWithSameAbbr = abbrToWordsMap[abbr];
26
27    if (!wordsWithSameAbbr) {
28        // If the abbreviation isn't in the map, the word is unique
29        return true;
30    }
31  
32    // A word is unique if it is the only word with its abbreviation
33    // or it's the only instance of that word with its abbreviation
34    return wordsWithSameAbbr.size === 1 && wordsWithSameAbbr.has(word);
35}
36
37/**
38 * Calculates an abbreviation for a word.
39 * @param word The word to generate the abbreviation for.
40 * @returns The abbreviation of the word.
41 */
42function getAbbreviation(word: string): string {
43    let n: number = word.length;
44    if (n < 3) {
45        // Words of length less than 3 are their own abbreviation
46        return word;
47    }
48    // Abbreviations are created by taking the first letter,
49    // the count of the number of characters in between,
50    // and the last letter
51    return word.charAt(0) + (n - 2).toString() + word.charAt(n - 1);
52}
53
Fast Track Your Learning with Our Quick Skills Quiz:

Given an array of 1,000,000 integers that is almost sorted, except for 2 pairs of integers. Which algorithm is fastest for sorting the array?

Time and Space Complexity

Time Complexity

  • __init__ function:

    • The constructor iterates through each word in the given dictionary to compute its abbreviation and store it. If n is the number of words and k is the average length of the words, the time complexity is O(n*k) because the abbreviation process for each word takes O(k) time, and it is done for all n words.
  • isUnique function:

    • This function computes the abbreviation of the input word (which takes O(k) time, where k is the length of the word), and then it checks whether this word is unique based on the abbreviation look-up in the dictionary. The look-up time in a hash table is O(1) on average, but in the worst case (if there are hash collisions), it could be O(n) where n is the number of elements in the hash table under the same hash bucket. Because we need to check if the word is in the set, this takes O(1) time on average if sets are implemented with a hash. Thus, the time complexity is O(k) on average.

Space Complexity

  • __init__ function:

    • The space complexity is O(n*k) because each word is stored in the set data structure, and there may be n words of average length k. In cases where the dictionary contains many words with the same abbreviation but they are different words, this might not be efficient.
  • isUnique function:

    • The space complexity is O(1) because no additional space is used besides the input word and the space used by the abbreviation. This does not grow with the size of the input dictionary.

Please note that the abbreviation calculation itself is considered a constant-time operation because although it varies with the length of the input word, it is bounded and does not grow with the size of the dictionary.

Learn more about how to find time and space complexity quickly.


Recommended Readings


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫