Skip to content

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 capitalization, 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

Solution 1: Hash Table

Thinking

A query maps to the word list by exact match, then case-insensitive match, then vowel-insensitive match, taking the earliest word at that level. Build three tables: the original set, the first lowercase occurrence, and the first occurrence after vowels become *. Each query probes the tables in that order.

We traverse the \(\textit{wordlist}\) and store the words in hash tables \(\textit{low}\) and \(\textit{pat}\) according to case-insensitive and vowel-insensitive rules, respectively. The key of \(\textit{low}\) is the lowercase form of the word, and the key of \(\textit{pat}\) is the string obtained by replacing the vowels of the word with *, with the value being the word itself. We use the hash table \(\textit{s}\) to store the words in \(\textit{wordlist}\).

We traverse \(\textit{queries}\), for each word \(\textit{q}\), if \(\textit{q}\) is in \(\textit{s}\), it means \(\textit{q}\) is in \(\textit{wordlist}\), and we directly add \(\textit{q}\) to the answer array \(\textit{ans}\); otherwise, if the lowercase form of \(\textit{q}\) is in \(\textit{low}\), it means \(\textit{q}\) is in \(\textit{wordlist}\) and is case-insensitive, and we add \(\textit{low}[q.\text{lower}()]\) to the answer array \(\textit{ans}\); otherwise, if the string obtained by replacing the vowels of \(\textit{q}\) with * is in \(\textit{pat}\), it means \(\textit{q}\) is in \(\textit{wordlist}\) and is vowel-insensitive, and we add \(\textit{pat}[f(q)]\) to the answer array \(\textit{ans}\); otherwise, it means \(\textit{q}\) is not in \(\textit{wordlist}\), and we add an empty string to the answer array \(\textit{ans}\).

Finally, we return the answer array \(\textit{ans}\).

The time complexity is \(O(n + m)\), and the space complexity is \(O(n)\), where \(n\) and \(m\) are the lengths of \(\textit{wordlist}\) and \(\textit{queries}\), respectively.

 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
28
29
30
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

 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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
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);
    }
}

 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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
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 (const auto& w : wordlist) {
            string t = w;
            transform(t.begin(), t.end(), t.begin(), ::tolower);
            if (!low.contains(t)) {
                low[t] = w;
            }
            t = f(t);
            if (!pat.contains(t)) {
                pat[t] = w;
            }
        }
        vector<string> ans;
        for (auto& q : queries) {
            if (s.contains(q)) {
                ans.emplace_back(q);
                continue;
            }
            transform(q.begin(), q.end(), q.begin(), ::tolower);
            if (low.contains(q)) {
                ans.emplace_back(low[q]);
                continue;
            }
            q = f(q);
            if (pat.contains(q)) {
                ans.emplace_back(pat[q]);
                continue;
            }
            ans.emplace_back("");
        }
        return ans;
    }
};

 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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
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
}

 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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
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;
}

 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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
use std::collections::{HashSet, HashMap};

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
    }
}

Comments