966. Vowel Spellchecker
Given a wordlist
, we want to implement a spellchecker that converts a query word into a correct word.
For a given query
word, the spell checker handles two categories of spelling mistakes:
- Capitalization: If the query matches a word in the wordlist (case-insensitive), then the query word is returned with the same case as the case in the wordlist.
- Example:
wordlist = ["yellow"]
,query = "YellOw"
:correct = "yellow"
- Example:
wordlist = ["Yellow"]
,query = "yellow"
:correct = "Yellow"
- Example:
wordlist = ["yellow"]
,query = "yellow"
:correct = "yellow"
- Example:
- Vowel Errors: If after replacing the vowels ('a', 'e', 'i', 'o', 'u') of the query word with any vowel individually, it matches a word in the wordlist (case-insensitive), then the query word is returned with the same case as the match in the wordlist.
- Example:
wordlist = ["YellOw"]
,query = "yollow"
:correct = "YellOw"
- Example:
wordlist = ["YellOw"]
,query = "yeellow"
:correct = ""
(no match) - Example:
wordlist = ["YellOw"]
,query = "yllw"
:correct = ""
(no match)
- Example:
In addition, the spell checker operates under the following precedence rules:
- When the query exactly matches a word in the wordlist (case-sensitive), you should return the same word back.
- When the query matches a word up to capitlization, you should return the first such match in the wordlist.
- When the query matches a word up to vowel errors, you should return the first such match in the wordlist.
- If the query has no matches in the wordlist, you should return the empty string.
Given some queries
, return a list of words answer
, where answer[i]
is the correct word for query = queries[i]
.
Example 1:
Input: wordlist = ["KiTe","kite","hare","Hare"], queries = ["kite","Kite","KiTe","Hare","HARE","Hear","hear","keti","keet","keto"] Output: ["kite","KiTe","KiTe","Hare","hare","","","KiTe","","KiTe"]
Note:
1 <= wordlist.length <= 5000
1 <= queries.length <= 5000
1 <= wordlist[i].length <= 7
1 <= queries[i].length <= 7
- All strings in
wordlist
andqueries
consist only of english letters.
Rust Solution
struct Solution;
use std::collections::hash_map::DefaultHasher;
use std::collections::HashMap;
use std::collections::HashSet;
use std::hash::Hasher;
struct Dict {
same: HashSet<String>,
capitlization: HashMap<u64, String>,
vowel_error: HashMap<u64, String>,
}
impl Dict {
fn new(wordlist: Vec<String>) -> Self {
let mut same: HashSet<String> = HashSet::new();
let mut capitlization: HashMap<u64, String> = HashMap::new();
let mut vowel_error: HashMap<u64, String> = HashMap::new();
for s in wordlist.iter().rev() {
same.insert(s.to_string());
capitlization.insert(Self::hash1(&s), s.to_string());
vowel_error.insert(Self::hash2(&s), s.to_string());
}
Dict {
same,
capitlization,
vowel_error,
}
}
fn query(&self, s: String) -> String {
if self.same.contains(&s) {
return s;
}
if let Some(res) = self.capitlization.get(&Self::hash1(&s)) {
return res.to_string();
}
if let Some(res) = self.vowel_error.get(&Self::hash2(&s)) {
return res.to_string();
}
"".to_string()
}
fn hash1(s: &str) -> u64 {
let mut hasher = DefaultHasher::new();
for c in s.to_lowercase().chars() {
hasher.write_u8(c as u8);
}
hasher.finish()
}
fn hash2(s: &str) -> u64 {
let mut hasher = DefaultHasher::new();
for c in s.to_lowercase().chars() {
let c = match c {
'a' | 'e' | 'i' | 'o' | 'u' => '_',
_ => c,
};
hasher.write_u8(c as u8);
}
hasher.finish()
}
}
impl Solution {
fn spellchecker(wordlist: Vec<String>, queries: Vec<String>) -> Vec<String> {
let dict = Dict::new(wordlist);
queries.into_iter().map(|s| dict.query(s)).collect()
}
}
#[test]
fn test() {
let wordlist = vec_string!["KiTe", "kite", "hare", "Hare"];
let queries =
vec_string!["kite", "Kite", "KiTe", "Hare", "HARE", "Hear", "hear", "keti", "keet", "keto"];
let res = vec_string!["kite", "KiTe", "KiTe", "Hare", "hare", "", "", "KiTe", "", "KiTe"];
assert_eq!(Solution::spellchecker(wordlist, queries), res);
}
Having problems with this solution? Click here to submit an issue on github.