Problem Description

The Unique Word Abbreviation problem asks you to design a data structure that can efficiently determine if a given word's abbreviation is unique within a provided dictionary of words.

The abbreviation of a word is defined as follows: For a word of length n, its abbreviation is the concatenation of its first letter, the number n - 2 (representing the number of characters between the first and last letter), and its last letter. If the word length is less than or equal to 2, the abbreviation is just the word itself.

You are given a list of words dictionary and must implement two operations:

• ValidWordAbbr(dictionary): Initializes the data structure with the given dictionary.
• isUnique(word): Returns true if the abbreviation of word is unique in the dictionary; otherwise, returns false.

Constraints:

• The dictionary may contain duplicate words.
• All words consist of lowercase English letters.
• You must not reuse elements in a way that violates the uniqueness requirement.

Thought Process

At first glance, the problem seems to require checking each word in the dictionary for every isUnique call, comparing abbreviations. This brute-force approach would be slow, especially for large dictionaries or many queries.

To optimize, we realize that abbreviations can be precomputed and mapped to their corresponding words. If we store, for each abbreviation, the set of words in the dictionary that share it, we can quickly answer uniqueness queries:

• If the abbreviation is not in the dictionary, any word is unique by default.
• If the abbreviation maps to a set containing only the queried word, it is unique.
• If there are other words with the same abbreviation, it is not unique.

Solution Approach

We'll solve the problem using a hash map (dictionary) to map abbreviations to the set of words in the dictionary that have that abbreviation.

1. Abbreviation Function: Write a helper function that returns the abbreviation for a given word, according to the rules described above.
2. Initialization: When constructing the data structure, iterate over the dictionary and for each word, compute its abbreviation and add the word to the set of words for that abbreviation in the map. Using a set prevents duplicates.
3. Uniqueness Check: For isUnique(word), compute the word's abbreviation and check:
   • If the abbreviation is not in the map, return true.
   • If the set for this abbreviation contains only the word itself, return true.
   • Otherwise, return false.
4. Why a Hash Map? The hash map allows O(1) lookups for abbreviations, making queries efficient.

Example Walkthrough

Let's walk through an example:

Dictionary: ["deer","door","cake","card"]

Abbreviations:

• "deer" → "d2r"
• "door" → "d2r"
• "cake" → "c2e"
• "card" → "c2d"

isUnique("dear"):

• Abbreviation: "d2r"
• In the dictionary, "d2r" maps to {"deer", "door"}
• Since "dear" is not in the set, return false

• Abbreviation: "c2t"
• Not in the map, so return true

• Abbreviation: "c2e"
• Set is {"cake"}; only "cake" itself, so return true

Time and Space Complexity

Brute-force Approach:

• Each isUnique call scans the entire dictionary: O(N) per query, where N is the number of words.
• Space: O(N) for storing the dictionary.

• Initialization: O(N * L), where L is the average word length (for computing abbreviations).
• Space: O(N), since each word is stored in at most one set per abbreviation.
• Query: O(1) per isUnique call, as hash map lookups and set length checks are constant time.

The optimized approach is much faster for repeated queries.

Summary

The Unique Word Abbreviation problem is efficiently solved by precomputing and mapping word abbreviations to sets of words using a hash map. This allows us to answer uniqueness queries in constant time, leveraging the power of hash-based data structures for fast lookups. The main insight is to shift from repeated scanning to smart preprocessing and O(1) queries, making the solution both elegant and scalable.

Code Implementation

class ValidWordAbbr:
    def __init__(self, dictionary):
        self.abbr_dict = {}
        self.dictionary = set(dictionary)
        for word in self.dictionary:
            abbr = self._abbr(word)
            if abbr not in self.abbr_dict:
                self.abbr_dict[abbr] = set()
            self.abbr_dict[abbr].add(word)

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

    def isUnique(self, word):
        abbr = self._abbr(word)
        if abbr not in self.abbr_dict:
            return True
        words = self.abbr_dict[abbr]
        return words == {word}
      

class ValidWordAbbr {
    unordered_map<string, unordered_set<string>> abbr_map;
public:
    ValidWordAbbr(vector<string>& dictionary) {
        unordered_set<string> dict(dictionary.begin(), dictionary.end());
        for (const string& word : dict) {
            string abbr = getAbbr(word);
            abbr_map[abbr].insert(word);
        }
    }

    string getAbbr(const string& word) {
        if (word.length() <= 2) return word;
        return word.front() + to_string(word.length() - 2) + word.back();
    }

    bool isUnique(string word) {
        string abbr = getAbbr(word);
        if (abbr_map.find(abbr) == abbr_map.end()) return true;
        const auto& words = abbr_map[abbr];
        return words.size() == 1 && words.count(word);
    }
};
      

import java.util.*;

class ValidWordAbbr {
    private Map<String, Set<String>> abbrMap;

    public ValidWordAbbr(String[] dictionary) {
        abbrMap = new HashMap<>();
        Set<String> dict = new HashSet<>(Arrays.asList(dictionary));
        for (String word : dict) {
            String abbr = abbr(word);
            abbrMap.computeIfAbsent(abbr, k -> new HashSet<>()).add(word);
        }
    }

    private String abbr(String word) {
        if (word.length() <= 2) return word;
        return "" + word.charAt(0) + (word.length() - 2) + word.charAt(word.length() - 1);
    }

    public boolean isUnique(String word) {
        String abbr = abbr(word);
        if (!abbrMap.containsKey(abbr)) return true;
        Set<String> words = abbrMap.get(abbr);
        return words.size() == 1 && words.contains(word);
    }
}
      

class ValidWordAbbr {
    constructor(dictionary) {
        this.abbrMap = new Map();
        this.dictionary = new Set(dictionary);
        for (let word of this.dictionary) {
            const abbr = this._abbr(word);
            if (!this.abbrMap.has(abbr)) {
                this.abbrMap.set(abbr, new Set());
            }
            this.abbrMap.get(abbr).add(word);
        }
    }

    _abbr(word) {
        if (word.length <= 2) return word;
        return word[0] + (word.length - 2) + word[word.length - 1];
    }

    isUnique(word) {
        const abbr = this._abbr(word);
        if (!this.abbrMap.has(abbr)) return true;
        const words = this.abbrMap.get(abbr);
        return words.size === 1 && words.has(word);
    }
}