Problem

The abbreviation of a word is a concatenation of its first letter, the number of characters between the first and last letter, and its last letter. If a word has only two characters, then it is an abbreviation of itself.

For example:

  • dog --> d1g because there is one letter between the first letter 'd' and the last letter 'g'.
  • internationalization --> i18n because there are 18 letters between the first letter 'i' and the last letter 'n'.
  • it --> it because any word with only two characters is an abbreviation of itself.

Implement the ValidWordAbbr class:

  • ValidWordAbbr(String[] dictionary) Initializes the object with a dictionary of words.
  • boolean isUnique(string word) Returns true if either of the following conditions are met (otherwise returns false):
    • There is no word in dictionary whose abbreviation is equal to word‘s abbreviation.
    • For any word in dictionary whose abbreviation is equal to word‘s abbreviation, that word and word are the same.

Examples

Example 1:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

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.

Solution

Method 1 - Using Hashmap

To solve this problem, we need to handle the abbreviation of words in a given dictionary and check if a given word’s abbreviation is unique based on certain conditions.

The abbreviation of a word is formed by:

  • The first letter.
  • The number of characters between the first and last letter.
  • The last letter.

For example, the abbreviation of "dog" is "d1g", and for "internationalization" it is "i18n". Words with exactly two letters are abbreviated to the word itself.

Approach

  1. Store Abbreviations:
    • Use a dictionary (or hashmap) to map abbreviations to the set of words that have that abbreviation.
  2. Initialization:
    • Create a ValidWordAbbr class that initializes the dictionary with the provided list of words.
  3. Check Uniqueness:
    • A method isUnique that checks for the uniqueness based on the following conditions:
      • If the abbreviation of the given word is not in the dictionary, return True.
      • If it is in the dictionary, check if the abbreviation maps to the exact same word or if there are no other words with that abbreviation.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

public class ValidWordAbbr {
    private Map<String, Set<String>> abbrevDict;

    public ValidWordAbbr(String[] dictionary) {
        abbrevDict = new HashMap<>();
        for (String word : dictionary) {
            String abbrev = getAbbreviation(word);
            if (!abbrevDict.containsKey(abbrev)) {
                abbrevDict.put(abbrev, new HashSet<>());
            }
            abbrevDict.get(abbrev).add(word);
        }
    }

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

    private String getAbbreviation(String word) {
        if (word.length() <= 2) {
            return word;
        }
        return word.charAt(0) + Integer.toString(word.length() - 2) + word.charAt(word.length() - 1);
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class ValidWordAbbr:
    def __init__(self, dictionary: List[str]) -> None:
        self.abbrev_dict = {}
        for word in dictionary:
            abbrev = self.get_abbreviation(word)
            if abbrev not in self.abbrev_dict:
                self.abbrev_dict[abbrev] = set()
            self.abbrev_dict[abbrev].add(word)

    def is_unique(self, word: str) -> bool:
        abbrev = self.get_abbreviation(word)
        if abbrev not in self.abbrev_dict:
            return True
        words = self.abbrev_dict[abbrev]
        return len(words) == 1 and word in words

    def get_abbreviation(self, word: str) -> str:
        if len(word) <= 2:
            return word
        return f"{word[0]}{len(word) - 2}{word[-1]}"

Complexity

  • ⏰ Time complexity: O(n) for initializing the dictionary with n words. O(1) for checking the uniqueness of a word.
  • 🧺 Space complexity: O(n) for storing the abbreviations.