Welcome to Subscribe On Youtube

966. Vowel Spellchecker

Description

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"]

Example 2:

Input: wordlist = ["yellow"], queries = ["YellOw"]
Output: ["yellow"]

 

Constraints:

  • 1 <= wordlist.length, queries.length <= 5000
  • 1 <= wordlist[i].length, queries[i].length <= 7
  • wordlist[i] and queries[i] consist only of only English letters.

Solutions

  • class Solution {
        public String[] spellchecker(String[] wordlist, String[] queries) {
            Set<String> s = new HashSet<>();
            Map<String, String> low = new HashMap<>();
            Map<String, String> pat = new HashMap<>();
            for (String w : wordlist) {
                s.add(w);
                String t = w.toLowerCase();
                low.putIfAbsent(t, w);
                pat.putIfAbsent(f(t), w);
            }
            int m = queries.length;
            String[] ans = new String[m];
            for (int i = 0; i < m; ++i) {
                String q = queries[i];
                if (s.contains(q)) {
                    ans[i] = q;
                    continue;
                }
                q = q.toLowerCase();
                if (low.containsKey(q)) {
                    ans[i] = low.get(q);
                    continue;
                }
                q = f(q);
                if (pat.containsKey(q)) {
                    ans[i] = pat.get(q);
                    continue;
                }
                ans[i] = "";
            }
            return ans;
        }
    
        private String f(String w) {
            char[] cs = w.toCharArray();
            for (int i = 0; i < cs.length; ++i) {
                char c = cs[i];
                if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u') {
                    cs[i] = '*';
                }
            }
            return String.valueOf(cs);
        }
    }
    
  • class Solution {
    public:
        vector<string> spellchecker(vector<string>& wordlist, vector<string>& queries) {
            unordered_set<string> s(wordlist.begin(), wordlist.end());
            unordered_map<string, string> low;
            unordered_map<string, string> pat;
            auto f = [](string& w) {
                string res;
                for (char& c : w) {
                    if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u') {
                        res += '*';
                    } else {
                        res += c;
                    }
                }
                return res;
            };
            for (auto& w : wordlist) {
                string t = w;
                transform(t.begin(), t.end(), t.begin(), ::tolower);
                if (!low.count(t)) {
                    low[t] = w;
                }
                t = f(t);
                if (!pat.count(t)) {
                    pat[t] = w;
                }
            }
            vector<string> ans;
            for (auto& q : queries) {
                if (s.count(q)) {
                    ans.emplace_back(q);
                    continue;
                }
                transform(q.begin(), q.end(), q.begin(), ::tolower);
                if (low.count(q)) {
                    ans.emplace_back(low[q]);
                    continue;
                }
                q = f(q);
                if (pat.count(q)) {
                    ans.emplace_back(pat[q]);
                    continue;
                }
                ans.emplace_back("");
            }
            return ans;
        }
    };
    
  • class Solution:
        def spellchecker(self, wordlist: List[str], queries: List[str]) -> List[str]:
            def f(w):
                t = []
                for c in w:
                    t.append("*" if c in "aeiou" else c)
                return "".join(t)
    
            s = set(wordlist)
            low, pat = {}, {}
            for w in wordlist:
                t = w.lower()
                low.setdefault(t, w)
                pat.setdefault(f(t), w)
    
            ans = []
            for q in queries:
                if q in s:
                    ans.append(q)
                    continue
                q = q.lower()
                if q in low:
                    ans.append(low[q])
                    continue
                q = f(q)
                if q in pat:
                    ans.append(pat[q])
                    continue
                ans.append("")
            return ans
    
    
  • func spellchecker(wordlist []string, queries []string) (ans []string) {
    	s := map[string]bool{}
    	low := map[string]string{}
    	pat := map[string]string{}
    	f := func(w string) string {
    		res := []byte(w)
    		for i := range res {
    			if res[i] == 'a' || res[i] == 'e' || res[i] == 'i' || res[i] == 'o' || res[i] == 'u' {
    				res[i] = '*'
    			}
    		}
    		return string(res)
    	}
    	for _, w := range wordlist {
    		s[w] = true
    		t := strings.ToLower(w)
    		if _, ok := low[t]; !ok {
    			low[t] = w
    		}
    		if _, ok := pat[f(t)]; !ok {
    			pat[f(t)] = w
    		}
    	}
    	for _, q := range queries {
    		if s[q] {
    			ans = append(ans, q)
    			continue
    		}
    		q = strings.ToLower(q)
    		if s, ok := low[q]; ok {
    			ans = append(ans, s)
    			continue
    		}
    		q = f(q)
    		if s, ok := pat[q]; ok {
    			ans = append(ans, s)
    			continue
    		}
    		ans = append(ans, "")
    	}
    	return
    }
    
  • function spellchecker(wordlist: string[], queries: string[]): string[] {
        const s = new Set(wordlist);
        const low = new Map<string, string>();
        const pat = new Map<string, string>();
    
        const f = (w: string): string => {
            let res = '';
            for (const c of w) {
                if ('aeiou'.includes(c)) {
                    res += '*';
                } else {
                    res += c;
                }
            }
            return res;
        };
    
        for (const w of wordlist) {
            let t = w.toLowerCase();
            if (!low.has(t)) {
                low.set(t, w);
            }
            t = f(t);
            if (!pat.has(t)) {
                pat.set(t, w);
            }
        }
    
        const ans: string[] = [];
        for (let q of queries) {
            if (s.has(q)) {
                ans.push(q);
                continue;
            }
            q = q.toLowerCase();
            if (low.has(q)) {
                ans.push(low.get(q)!);
                continue;
            }
            q = f(q);
            if (pat.has(q)) {
                ans.push(pat.get(q)!);
                continue;
            }
            ans.push('');
        }
        return ans;
    }
    
    
  • use std::collections::{HashMap, HashSet};
    
    impl Solution {
        pub fn spellchecker(wordlist: Vec<String>, queries: Vec<String>) -> Vec<String> {
            let s: HashSet<String> = wordlist.iter().cloned().collect();
            let mut low: HashMap<String, String> = HashMap::new();
            let mut pat: HashMap<String, String> = HashMap::new();
    
            let f = |w: &str| -> String {
                w.chars()
                    .map(|c| match c {
                        'a' | 'e' | 'i' | 'o' | 'u' => '*',
                        _ => c,
                    })
                    .collect()
            };
    
            for w in &wordlist {
                let mut t = w.to_lowercase();
                if !low.contains_key(&t) {
                    low.insert(t.clone(), w.clone());
                }
                t = f(&t);
                if !pat.contains_key(&t) {
                    pat.insert(t.clone(), w.clone());
                }
            }
    
            let mut ans: Vec<String> = Vec::new();
            for query in queries {
                if s.contains(&query) {
                    ans.push(query);
                    continue;
                }
                let mut q = query.to_lowercase();
                if let Some(v) = low.get(&q) {
                    ans.push(v.clone());
                    continue;
                }
                q = f(&q);
                if let Some(v) = pat.get(&q) {
                    ans.push(v.clone());
                    continue;
                }
                ans.push("".to_string());
            }
            ans
        }
    }
    
    

All Problems

All Solutions