Unique Word Abbreviation

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

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);
    }
}