288. Unique Word Abbreviation π
Description
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 adictionary
of words.boolean isUnique(string word)
Returnstrue
if either of the following conditions are met (otherwise returnsfalse
):- There is no word in
dictionary
whose abbreviation is equal toword
's abbreviation. - For any word in
dictionary
whose abbreviation is equal toword
's abbreviation, that word andword
are the same.
- There is no word in
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 * 104
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
.
Solutions
Solution 1: Hash Table
According to the problem description, we define a function $abbr(s)$, which calculates the abbreviation of the word $s$. If the length of the word $s$ is less than $3$, then its abbreviation is itself; otherwise, its abbreviation is its first letter + (its length - 2) + its last letter.
Next, we define a hash table $d$, where the key is the abbreviation of the word, and the value is a set, the elements of which are all words abbreviated as that key. We traverse the given word dictionary, and for each word $s$ in the dictionary, we calculate its abbreviation $abbr(s)$, and add $s$ to $d[abbr(s)]$.
When judging whether the word $word$ meets the requirements of the problem, we calculate its abbreviation $abbr(word)$. If $abbr(word)$ is not in the hash table $d$, then $word$ meets the requirements of the problem; otherwise, we judge whether there is only one element in $d[abbr(word)]$. If there is only one element in $d[abbr(word)]$ and that element is $word$, then $word$ meets the requirements of the problem.
In terms of time complexity, the time complexity of initializing the hash table is $O(n)$, where $n$ is the length of the word dictionary; the time complexity of judging whether a word meets the requirements of the problem is $O(1)$. In terms of space complexity, the space complexity of the hash table is $O(n)$.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
|
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 |
|
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 |
|