LeetCode 288: Unique Word Abbreviation

Explanation

To solve this problem, we can use a hashmap to store the abbreviations of words as keys and the corresponding word as the value. When checking if an abbreviation is unique, we can iterate through the hashmap and check if the abbreviation already exists. If it does, we need to verify if the value associated with that abbreviation is the same as the current word. If it is not the same, then the abbreviation is not unique.

Algorithm:

1. Create a hashmap to store the abbreviations of words.
2. For each word in the dictionary:
   • Generate the abbreviation of the word.
   • Check if the abbreviation already exists in the hashmap:
     • If it does, check if the corresponding word is the same as the current word.
     • If it is not the same, then the abbreviation is not unique.
     • If it is the same, continue to the next word.
   • If the abbreviation does not exist in the hashmap, add it to the hashmap.
3. When checking if an abbreviation is unique, return true if it is unique, false otherwise.

Time Complexity

The time complexity of this approach is O(n) where n is the number of words in the dictionary. This is because we iterate through each word in the dictionary and perform constant time operations.

Space Complexity

The space complexity of this approach is O(n) where n is the number of unique abbreviations stored in the hashmap.

class ValidWordAbbr {
    Map<String, String> map;

    public ValidWordAbbr(String[] dictionary) {
        map = new HashMap<>();
        for (String word : dictionary) {
            String abbr = generateAbbreviation(word);
            if (map.containsKey(abbr) && !map.get(abbr).equals(word)) {
                map.put(abbr, "");
            } else {
                map.put(abbr, word);
            }
        }
    }

    public boolean isUnique(String word) {
        String abbr = generateAbbreviation(word);
        return !map.containsKey(abbr) || map.get(abbr).equals(word);
    }

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