Unique Word Abbreviation

Updated on 03 July, 2025
Unique Word Abbreviation header image

Problem Statement

The concept of abbreviating a word involves alternatively concatenating the first letter, the numerical count of letters between the first and last letter, and finally the last letter of the word itself. To illustrate, the abbreviation for "dog" is "d1g" since there's one letter between 'd' and 'g'. When the word length is only two, the abbreviation is the word itself, like "it" becomes "it".

This challenge involves implementing a class named ValidWordAbbr. This class should:

  1. Utilize a constructor ValidWordAbbr(String[] dictionary) that initializes the class with a predefined list of words.

  2. Include a method boolean isUnique(string word) that evaluates if a word's abbreviation is unique in two scenarios:

    • No existing word in the dictionary shares the same abbreviation.
    • If any dictionary word shares the abbreviation, it must be the exact same word as the query.

Examples

Example 1

Input:

["ValidWordAbbr", "isUnique", "isUnique", "isUnique", "isUnique", "isUnique"]
[[["deer", "door", "cake", "card"]], ["dear"], ["cart"], ["cane"], ["make"], ["cake"]]

Output:

[null, false, true, false, true, true]

Explanation:

ValidWordAbbr validWordAbbr = new ValidWordAbbr(["deer", "door", "cake", "card"]);
validWordAbbr.isUnique("dear"); // return false, dictionary word "deer" and word "dear" have the same abbreviation "d2r" but are not the same.
validWordAbbr.isUnique("cart"); // return true, no words in the dictionary have the abbreviation "c2t".
validWordAbbr.isUnique("cane"); // return false, dictionary word "cake" and word "cane" have the same abbreviation "c2e" but are not the same.
validWordAbbr.isUnique("make"); // return true, no words in the dictionary have the abbreviation "m2e".
validWordAbbr.isUnique("cake"); // return true, because "cake" is already in the dictionary and no other word in the dictionary has "c2e" abbreviation.

Constraints

  • 1 <= dictionary.length <= 3 * 10^4
  • 1 <= dictionary[i].length <= 20
  • dictionary[i] consists of lowercase English letters.
  • 1 <= word.length <= 20
  • word consists of lowercase English letters.
  • At most 5000 calls will be made to isUnique.

Approach and Intuition

To effectively implement the ValidWordAbbr class functionality, particularly focusing on the uniqueness check of word abbreviations within the dictionary, we'll follow these steps:

  1. Initialization of the Dictionary During the instantiation of the class with a dictionary parameter, process each word to generate its abbreviation. Maintain a mapping (using a dictionary or hashmap) where the key is the abbreviation and the value is a set of words that share this abbreviation. This helps in efficiently checking for uniqueness later.

  2. Abbreviation Generation Method Define a helper function to compute the abbreviation for a given word according to the rules set out. This function will check the word length:

    • If the length is 2 or less, return the word itself as the abbreviation.
    • Otherwise, return the first letter, the number of in-between letters, and the last letter as the format.
  3. Uniqueness Check (isUnique method) Use the abbreviation generation method to derive the abbreviation of the word to be checked.

    • Check if the abbreviation is present in the dictionary:

      • If not, return true indicating uniqueness.

      • If present, check the set of words for this abbreviation:

        • If the set contains only the given word, and no other, return true.
        • Otherwise, return false.

These steps provide an efficient system to determine whether a given word's abbreviated form is unique within the constraints of the provided 'dictionary' after initialization. This approach efficiently utilizes data structures to minimize time complexity, particularly for large dictionaries and numerous calls to isUnique.

Solutions

  • Java
java
public class WordAbbreviator {
    private final Map<String, Boolean> abbreviationMap = new HashMap<>();
    private final Set<String> originalWords;
    
    public WordAbbreviator(String[] words) {
        originalWords = new HashSet<>(Arrays.asList(words));
        for (String word : originalWords) {
            String abbreviation = createAbbreviation(word);
            abbreviationMap.put(abbreviation, !abbreviationMap.containsKey(abbreviation));
        }
    }
    
    public boolean isUnique(String query) {
        String abbreviation = createAbbreviation(query);
        Boolean uniqueStatus = abbreviationMap.get(abbreviation);
        return uniqueStatus == null || (uniqueStatus && originalWords.contains(query));
    }
    
    private String createAbbreviation(String word) {
        int len = word.length();
        if (len <= 2) {
            return word;
        }
        return word.charAt(0) + Integer.toString(len - 2) + word.charAt(len - 1);
    }
}

This Java solution handles the problem of determining whether a word's abbreviation is unique compared to a pre-defined list of words. The approach involves using a combination of a HashMap and HashSet to efficiently map abbreviations to their uniqueness and store the original words, respectively.

The class WordAbbreviator is defined with the following components:

  • abbreviationMap: A HashMap that stores the abbreviation as a key and a Boolean indicating its uniqueness as the value.
  • originalWords: A HashSet used to store the original list of words provided at the initialization of the class.

In the constructor WordAbbreviator(String[] words), initialize originalWords with the list of words. Iterate over these words to compute their abbreviations with the method createAbbreviation(String word). For each word's abbreviation:

  • Check if it has already been encountered with abbreviationMap.containsKey(abbreviation).
  • If the abbreviation is new, store it in the map with a value of true; if it exists already, update the value to false indicating it's not unique.

The createAbbreviation(String word) method generates the abbreviation:

  • If the word length is 2 or less, return the word itself.
  • Otherwise, construct the abbreviation by using the first letter, the count of intermediate characters, and the last letter of the word.

The method isUnique(String query) determines if an abbreviation is unique:

  • Generate the abbreviation for the query.
  • Check in abbreviationMap for the abbreviation's unique status:
    • If not present, it's considered unique because it was never mapped.
    • If marked true and the original set contains the query, it remains unique.
    • Otherwise, it is not unique.

This setup offers efficient query performance due to the constant time complexity of hash operations, making it suitable for systems that require quick checks against a pre-existing list of words.

Comments

No comments yet.