Leetcode 288. Unique Word Abbreviation

Problem Explanation

The problem is asking to find whether a word's abbreviation is unique in the dictionary. A word's abbreviation is unique if no other word from the dictionary has the same abbreviation. The word is abbreviated as the first letter, a number indicating the number of letters in between the first and last letter, and then the last letter.

For example, the word "dear" is abbreviated as "d2r", "door" as "d2r", "cake" as "c2e", "card" as "c2d", and so forth.

An abbreviation of a word is considered unique if it is not used by any other word in the dictionary. For instance, in the dictionary ["deer", "door", "cake", "card"], the abbreviation "d2r" is not unique because it is used by the words "deer" and "door". On the other hand, the abbreviation "c2e" is unique because it is only used by the word "cake".

Solution Approach

The solution to this problem involves using a hash map to store the abbreviations of all the words in the dictionary. The keys of the hash map are the abbreviations, and the values are the original words.

The class constructor builds the dictionary, where we initialize the hash map by populating it with the abbreviations and their corresponding words.

The isUnique method checks if a given word's abbreviation is unique in the dictionary. It does this by checking if the word's abbreviation is present in the hash map, and if it is, it verifies whether the associated word in the dictionary matches the input word.

In the class, we also have a helper function getAbbr that returns the abbreviation of a given word.

The solution makes use of the Hash Map data structure for easy and efficient access and update of word and abbreviation entries in the dictionary. This approach ensures we have O(1) time complexity for querying whether a word's abbreviation is unique.

Walkthrough an Example

Let's take an example dictionary=["door", "cake", "deer", "card"] and we want to check if the abbreviation of "dear" is unique.

1. First, we use the constructor to create the dictionary. The dictionary looks like this:

   1

plaintext { "d2r": "door", "c2e": "cake", "d2r": "deer", "c2d": "card", } ```

2. Now, we want to check if "dear" is unique. We find that the abbreviation for "dear" is "d2r". Checking in our dictionary, we find that there are two words with the same abbreviation, "door" and "deer". Thus "dear" is not unique. So, isUnique("dear") would return false.

Python Solution

1
2python
3class ValidWordAbbr:
4    def __init__(self, dictionary: list):
5        self.dictionary = {self._abbr(word): word for word in set(dictionary)}
6        
7    def isUnique(self, word: str) -> bool:
8        abbr = self._abbr(word)
9        return abbr not in self.dictionary or self.dictionary[abbr] == word
10
11    def _abbr(self, word: str) -> str:
12        if len(word) <= 2: return word
13        return word[0] + str(len(word) - 2) + word[-1]

Java Solution

1
2java
3import java.util.*;
4
5class ValidWordAbbr {
6  private final Map<String, String> dictionary;
7
8  public ValidWordAbbr(String[] dictionary) {
9    this.dictionary = new HashMap<>();
10    for(String word : new HashSet<>(Arrays.asList(dictionary))){
11      String abbr = abbr(word);
12      if(this.dictionary.containsKey(abbr) && !this.dictionary.get(abbr).equals(word)) this.dictionary.put(abbr, ""); 
13      else this.dictionary.put(abbr, word);
14    }
15  }
16
17  public boolean isUnique(String word) {
18    String abbr = abbr(word);
19    return !this.dictionary.containsKey(abbr) || this.dictionary.get(abbr).equals(word);
20  }
21
22  private String abbr(String word) {
23    if (word.length() <= 2) return word;
24    return word.charAt(0) + Integer.toString(word.length() - 2) + word.charAt(word.length() - 1);
25  }
26}

Javascript Solution

1
2javascript
3class ValidWordAbbr {
4  constructor(dictionary) {
5    this.dictionary = {};
6    for (let word of new Set(dictionary)) {
7      const abbr = this._abbr(word);
8      this.dictionary[abbr] = this.dictionary[abbr] ? "" : word;
9    }
10  }
11
12  isUnique(word) {
13    const abbr = this._abbr(word);
14    return !this.dictionary[abbr] || this.dictionary[abbr] === word;
15  }
16
17  _abbr(word) {
18    if (word.length <= 2) return word;
19    return word[0] + (word.length - 2) + word[word.length - 1];
20  }
21}

C++ Solution

1
2cpp
3#include<unordered_map>
4#include<set>
5#include<string>
6
7class ValidWordAbbr {
8public:
9  ValidWordAbbr(vector<string>& dictionary) {
10    for (const auto& word: set<string>(dictionary.begin(), dictionary.end())) {
11      string abbr = abbrv(word);
12      dict[abbr] = dict.count(abbr) && dict[abbr] != word ? "" : word;
13    }
14  }
15
16  bool isUnique(string word) {
17    string abbr = abbrv(word);
18    return !dict.count(abbr) || dict[abbr] == word;
19  }
20
21private:
22  unordered_map<string, string> dict;
23
24  string abbrv(string s) {
25    int n = s.size();
26    return n <= 2 ? s : s[0] + to_string(n - 2) + s[n - 1];
27  }
28};

C# Solution

1
2cs
3using System;
4using System.Collections.Generic;
5
6public class ValidWordAbbr {
7  private Dictionary<string, string> dictionary;
8
9  public ValidWordAbbr(string[] dictionary) {
10    this.dictionary = new Dictionary<string, string>();
11    foreach (var word in new HashSet<string>(dictionary)) {
12      var abbr = Abbr(word);
13      if (this.dictionary.ContainsKey(abbr) && this.dictionary[abbr] != word)
14        this.dictionary[abbr] = "";
15      else
16        this.dictionary[abbr] = word;
17    }
18  }
19
20  public bool IsUnique(string word) {
21    var abbr = Abbr(word);
22    return !this.dictionary.ContainsKey(abbr) || this.dictionary[abbr] == word;
23  }
24
25  private string Abbr(string word) {
26    if (word.Length <= 2) return word;
27    return word.Substring(0, 1) + (word.Length - 2) + word.Substring(word.Length - 1, 1);
28  }
29}

Testing the Solutions

Now, with the solutions all written, we can test each of them.

In Python, you can run the solution like this:

1
2python
3dictionary = ["deer","door","cake","card"]
4validWordAbbr = ValidWordAbbr(dictionary)
5print(validWordAbbr.isUnique("door"))  # It should return False
6print(validWordAbbr.isUnique("cart"))  # It should return True

In Java:

1
2java
3String[] dictionary = {"deer","door","cake","card"};
4ValidWordAbbr validWordAbbr = new ValidWordAbbr(dictionary);
5System.out.println(validWordAbbr.isUnique("door"));  // It should print False
6System.out.println(validWordAbbr.isUnique("cart"));  // It should print True

And similarly, in JavaScript:

1
2javascript
3const dictionary = ["deer","door","cake","card"];
4const validWordAbbr = new ValidWordAbbr(dictionary);
5console.log(validWordAbbr.isUnique("door"));  // It should log False
6console.log(validWordAbbr.isUnique("cart"));  // It should log True

In C++, you can create a vector with the dictionary words and check if a word is unique like this:

1
2cpp
3vector<string> dictionary = {"deer","door","cake","card"};
4ValidWordAbbr validWordAbbr(dictionary);
5cout << boolalpha << validWordAbbr.isUnique("door");  // It should print False
6cout << boolalpha << validWordAbbr.isUnique("cart");  // It should print True

Lastly, in C# you can test the solution as follows:

1
2cs
3string[] dictionary = {"deer","door","cake","card"};
4ValidWordAbbr validWordAbbr = new ValidWordAbbr(dictionary);
5Console.WriteLine(validWordAbbr.IsUnique("door"));  // It should print False
6Console.WriteLine(validWordAbbr.IsUnique("cart"));  // It should print True

By testing your solution with different parameters, you can ensure it works for all edge cases, giving you a robust and valid solution.

Conclusion

Solving this problem helps to better understand the manipulation of strings and the utilization of HashMaps. Both are crucial concepts in computer science and are frequently used in software engineering. This problem is an excellent representative of interview questions that have a minor twist in the core concept.

• The knowledge of transforming each word into its corresponding abbreviation using the string manipulation concept is the first step towards the solution.
• Afterward, understanding how to utilize HashMaps to remember each word and its abbreviation to reduce the computational complexity was the critical step toward an optimized solution. It made querying very efficient and saved a lot of time when checking whether a word's abbreviation is unique.

So, problems like this help to sharpen one's ability to use data structures like the hash map or dictionary, which is a valuable skill in competitive programming and coding interviews.