288. Unique Word Abbreviation
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"] [[["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, 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
.
Rust Solution
use std::collections::hash_map::DefaultHasher;
use std::collections::HashMap;
use std::collections::HashSet;
use std::hash::Hasher;
struct ValidWordAbbr {
abbr: HashMap<u64, HashSet<String>>,
}
impl ValidWordAbbr {
fn new(dictionary: Vec<String>) -> Self {
let mut abbr: HashMap<u64, HashSet<String>> = HashMap::new();
for s in dictionary {
let hash = Self::abbr_hash(&s);
abbr.entry(hash).or_default().insert(s);
}
ValidWordAbbr { abbr }
}
fn abbr_hash(s: &str) -> u64 {
let s: Vec<u8> = s.bytes().collect();
let n = s.len();
let mut hasher = DefaultHasher::new();
if !s.is_empty() {
hasher.write_u8(s[0]);
hasher.write_usize(s.len());
hasher.write_u8(s[n - 1]);
hasher.finish()
} else {
0
}
}
fn is_unique(&self, word: String) -> bool {
let hash = Self::abbr_hash(&word);
if let Some(set) = self.abbr.get(&hash) {
set.contains(&word) && set.len() == 1
} else {
true
}
}
}
#[test]
fn test() {
let obj = ValidWordAbbr::new(vec_string!["deer", "door", "cake", "card"]);
assert_eq!(obj.is_unique("dear".to_string()), false);
assert_eq!(obj.is_unique("cart".to_string()), true);
assert_eq!(obj.is_unique("cane".to_string()), false);
assert_eq!(obj.is_unique("make".to_string()), true);
assert_eq!(obj.is_unique("door".to_string()), false);
}
Having problems with this solution? Click here to submit an issue on github.