RUST GYM v0.2.4

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"
  • 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)

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 and queries 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.