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:
"word" -> "w2d""a" -> "a""ab" -> "ab"The valid word abbreviation of a word must be unambiguous. Meaning that only one word can have the same abbreviation.
Implement the ValidWordAbbr class:
ValidWordAbbr(String[] dictionary) Initializes the object with a dictionary of words.boolean isUnique(String word) Returns true if the abbreviation of word is unique in the dictionary, or false otherwise.Example 1:
Input
["ValidWordAbbr", "isUnique", "isUnique", "isUnique", "isUnique"]
[[["deer", "door", "cake", "card"]], ["dear"], ["cart"], ["cane"], ["make"]]
Output
[null, false, true, false, true]
Explanation
ValidWordAbbr validWordAbbr = new ValidWordAbbr(["deer", "door", "cake", "card"]);
validWordAbbr.isUnique("dear"); // return false, the abbreviation "d2r" is ambiguous.
validWordAbbr.isUnique("cart"); // return true, the abbreviation "c2t" is unique.
validWordAbbr.isUnique("cane"); // return false, the abbreviation "c2e" is ambiguous.
validWordAbbr.isUnique("make"); // return true, the abbreviation "m2e" is unique.
Constraints:
1 <= dictionary.length <= 1001 <= dictionary[i].length <= 20dictionary[i] consists of lowercase English letters.1 <= word.length <= 20word consists of lowercase English letters.5000 calls will be made to isUnique.When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:
We're given a word and a dictionary of words. The goal is to see if the word's abbreviation is unique among the words in the dictionary. The brute force approach is to check the abbreviation against every word in the dictionary.
Here's how the algorithm would work step-by-step:
def is_unique_word_abbreviation_brute_force(word, dictionary):
word_abbreviation = create_abbreviation(word)
for dictionary_word in dictionary:
# Iterate through the dictionary
dictionary_word_abbreviation = create_abbreviation(dictionary_word)
# Crucial step: check if abbr same but words different
if word_abbreviation == dictionary_word_abbreviation and word != dictionary_word:
return False
# If we went through the whole dictionary and didn't find a match
return True
def create_abbreviation(word):
word_length = len(word)
if word_length <= 2:
return word
# Abbreviate only if length > 2, as per problem
abbreviation = word[0] + str(word_length - 2) + word[-1]
return abbreviationThe goal is to determine if a given abbreviation is unique compared to a dictionary of words. The efficient approach involves pre-processing the dictionary to store possible abbreviations and quickly check if the given abbreviation exists for other words.
Here's how the algorithm would work step-by-step:
class ValidWordAbbr:
def __init__(self, dictionary: list[str]):
self.abbreviation_map = {}
for word in dictionary:
abbreviation = self.to_abbreviation(word)
# Track words with the same abbreviation.
if abbreviation in self.abbreviation_map:
self.abbreviation_map[abbreviation].add(word)
else:
self.abbreviation_map[abbreviation] = {word}
def isUnique(self, word: str) -> bool:
abbreviation = self.to_abbreviation(word)
# Check if the abbreviation exists.
if abbreviation not in self.abbreviation_map:
return True
# Ensure the abbreviation is only used by the current word.
return self.abbreviation_map[abbreviation] == {word}
def to_abbreviation(self, word: str) -> str:
word_length = len(word)
# No abbreviation needed for short words.
if word_length <= 2:
return word
first_letter = word[0]
last_letter = word[-1]
middle_length = word_length - 2
return f"{first_letter}{middle_length}{last_letter}"| Case | How to Handle |
|---|---|
| Empty dictionary | Return true, because no words conflict with the abbreviation. |
| Word is longer than abbreviation length | Return false because any abbreviation is always smaller or equal to the actual word. |
| Word is exactly the same as the abbreviation. | Return true if and only if the word is in the dictionary and dictionary size is 1. |
| Abbreviation is empty string | Return false if any word in dictionary is non-empty, otherwise true. |
| Dictionary contains multiple words which can be abbreviated to the same abbreviation as the word. | Return false because there is a conflict in abbreviations within the dictionary. |
| Word in dictionary is the same word. | If dictionary size is 1, then the word should be valid, else there are conflicting words. |
| Word is null | Handle null word case by throwing IllegalArgumentException or considering it as an empty string depending on the context. |
| Dictionary word is null | Handle null word in dictionary by skipping that word or throwing an error depending on the desired behavior. |