
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:
Utilize a constructor
ValidWordAbbr(String[] dictionary)
that initializes the class with a predefined list of words.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 toisUnique
.
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:
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.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.
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
.
- If the set contains only the given word, and no other, return
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
- Java
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);
}
}
This Java solution handles the problem of determining whether a word's abbreviation is unique compared to a pre-defined list of words. The approach involves using a combination of a HashMap and HashSet to efficiently map abbreviations to their uniqueness and store the original words, respectively.
The class WordAbbreviator
is defined with the following components:
abbreviationMap
: A HashMap that stores the abbreviation as a key and a Boolean indicating its uniqueness as the value.originalWords
: A HashSet used to store the original list of words provided at the initialization of the class.
In the constructor WordAbbreviator(String[] words)
, initialize originalWords
with the list of words. Iterate over these words to compute their abbreviations with the method createAbbreviation(String word)
. For each word's abbreviation:
- Check if it has already been encountered with
abbreviationMap.containsKey(abbreviation)
. - If the abbreviation is new, store it in the map with a value of true; if it exists already, update the value to false indicating it's not unique.
The createAbbreviation(String word)
method generates the abbreviation:
- If the word length is 2 or less, return the word itself.
- Otherwise, construct the abbreviation by using the first letter, the count of intermediate characters, and the last letter of the word.
The method isUnique(String query)
determines if an abbreviation is unique:
- Generate the abbreviation for the query.
- Check in
abbreviationMap
for the abbreviation's unique status:- If not present, it's considered unique because it was never mapped.
- If marked true and the original set contains the query, it remains unique.
- Otherwise, it is not unique.
This setup offers efficient query performance due to the constant time complexity of hash operations, making it suitable for systems that require quick checks against a pre-existing list of words.
No comments yet.