Vowel Spellchecker

Problem

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

Examples

Example 1

1
2


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

1
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.

Solution

Method 1 – Hash Maps and Vowel Masking

Intuition

Use hash maps to store exact, case-insensitive, and vowel-masked versions of the wordlist for fast lookup. For each query, check in order: exact match, case-insensitive match, vowel-error match.

Approach

Build three maps:
- Exact words (set)
- Lowercase words (first occurrence)
- Vowel-masked words (first occurrence)
For each query, check in order: exact, lowercase, vowel-masked.

Code

 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


#include <vector>
#include <string>
#include <unordered_set>
#include <unordered_map>
using namespace std;
string devowel(const string& w) {
    string res = w;
    for (char& c : res) if (string("aeiouAEIOU").find(c) != string::npos) c = '*';
    return res;
}
class Solution {
public:
    vector<string> spellchecker(vector<string>& wordlist, vector<string>& queries) {
        unordered_set<string> exact(wordlist.begin(), wordlist.end());
        unordered_map<string, string> lower, vowel;
        for (const string& w : wordlist) {
            string wl = w;
            for (auto& c : wl) c = tolower(c);
            if (!lower.count(wl)) lower[wl] = w;
            string vw = devowel(wl);
            if (!vowel.count(vw)) vowel[vw] = w;
        }
        vector<string> res;
        for (const string& q : queries) {
            if (exact.count(q)) res.push_back(q);
            else {
                string ql = q;
                for (auto& c : ql) c = tolower(c);
                if (lower.count(ql)) res.push_back(lower[ql]);
                else {
                    string vq = devowel(ql);
                    if (vowel.count(vq)) res.push_back(vowel[vq]);
                    else res.push_back("");
                }
            }
        }
        return res;
    }
};

 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


import "strings"
func devowel(w string) string {
    res := []rune(w)
    for i, c := range res {
        if strings.ContainsRune("aeiouAEIOU", c) {
            res[i] = '*'
        }
    }
    return string(res)
}
func spellchecker(wordlist []string, queries []string) []string {
    exact := make(map[string]struct{})
    lower := make(map[string]string)
    vowel := make(map[string]string)
    for _, w := range wordlist {
        wl := strings.ToLower(w)
        if _, ok := lower[wl]; !ok {
            lower[wl] = w
        }
        vw := devowel(wl)
        if _, ok := vowel[vw]; !ok {
            vowel[vw] = w
        }
        exact[w] = struct{}{}
    }
    res := make([]string, len(queries))
    for i, q := range queries {
        if _, ok := exact[q]; ok {
            res[i] = q
        } else if v, ok := lower[strings.ToLower(q)]; ok {
            res[i] = v
        } else if v, ok := vowel[devowel(strings.ToLower(q))]; ok {
            res[i] = v
        } else {
            res[i] = ""
        }
    }
    return res
}

 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


import java.util.*;
class Solution {
    public String[] spellchecker(String[] wordlist, String[] queries) {
        Set<String> exact = new HashSet<>(Arrays.asList(wordlist));
        Map<String, String> lower = new HashMap<>();
        Map<String, String> vowel = new HashMap<>();
        for (String w : wordlist) {
            String wl = w.toLowerCase();
            lower.putIfAbsent(wl, w);
            String vw = devowel(wl);
            vowel.putIfAbsent(vw, w);
        }
        String[] res = new String[queries.length];
        for (int i = 0; i < queries.length; i++) {
            String q = queries[i];
            if (exact.contains(q)) res[i] = q;
            else if (lower.containsKey(q.toLowerCase())) res[i] = lower.get(q.toLowerCase());
            else if (vowel.containsKey(devowel(q.toLowerCase()))) res[i] = vowel.get(devowel(q.toLowerCase()));
            else res[i] = "";
        }
        return res;
    }
    private String devowel(String w) {
        StringBuilder sb = new StringBuilder();
        for (char c : w.toCharArray()) {
            sb.append("aeiou".indexOf(c) >= 0 ? '*' : c);
        }
        return sb.toString();
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


class Solution {
    fun spellchecker(wordlist: Array<String>, queries: Array<String>): Array<String> {
        fun devowel(w: String) = w.lowercase().map { if (it in "aeiou") '*' else it }.joinToString("")
        val exact = wordlist.toSet()
        val lower = mutableMapOf<String, String>()
        val vowel = mutableMapOf<String, String>()
        for (w in wordlist) {
            val wl = w.lowercase()
            lower.putIfAbsent(wl, w)
            val vw = devowel(w)
            vowel.putIfAbsent(vw, w)
        }
        return queries.map { q ->
            when {
                q in exact -> q
                lower.containsKey(q.lowercase()) -> lower[q.lowercase()]!!
                vowel.containsKey(devowel(q)) -> vowel[devowel(q)]!!
                else -> ""
            }
        }.toTypedArray()
    }
}

 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


from typing import List
class Solution:
    def spellchecker(self, wordlist: List[str], queries: List[str]) -> List[str]:
        def devowel(word):
            return ''.join('*' if c in 'aeiou' else c for c in word.lower())
        exact = set(wordlist)
        lower = {}
        vowel = {}
        for w in wordlist:
            wl = w.lower()
            if wl not in lower:
                lower[wl] = w
            vw = devowel(w)
            if vw not in vowel:
                vowel[vw] = w
        res = []
        for q in queries:
            if q in exact:
                res.append(q)
            elif q.lower() in lower:
                res.append(lower[q.lower()])
            elif devowel(q) in vowel:
                res.append(vowel[devowel(q)])
            else:
                res.append("")
        return res

 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


use std::collections::{HashSet, HashMap};
fn devowel(w: &str) -> String {
    w.chars().map(|c| if "aeiouAEIOU".contains(c) { '*' } else { c }).collect()
}
pub fn spellchecker(wordlist: Vec<String>, queries: Vec<String>) -> Vec<String> {
    let exact: HashSet<_> = wordlist.iter().cloned().collect();
    let mut lower = HashMap::new();
    let mut vowel = HashMap::new();
    for w in &wordlist {
        let wl = w.to_lowercase();
        lower.entry(wl.clone()).or_insert(w.clone());
        let vw = devowel(&wl);
        vowel.entry(vw).or_insert(w.clone());
    }
    queries.iter().map(|q| {
        if exact.contains(q) {
            q.clone()
        } else if let Some(w) = lower.get(&q.to_lowercase()) {
            w.clone()
        } else if let Some(w) = vowel.get(&devowel(&q.to_lowercase())) {
            w.clone()
        } else {
            String::new()
        }
    }).collect()
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


function devowel(w: string): string {
    return w.toLowerCase().replace(/[aeiou]/g, '*');
}
function spellchecker(wordlist: string[], queries: string[]): string[] {
    const exact = new Set(wordlist);
    const lower = new Map<string, string>();
    const vowel = new Map<string, string>();
    for (const w of wordlist) {
        const wl = w.toLowerCase();
        if (!lower.has(wl)) lower.set(wl, w);
        const vw = devowel(wl);
        if (!vowel.has(vw)) vowel.set(vw, w);
    }
    return queries.map(q => {
        if (exact.has(q)) return q;
        const ql = q.toLowerCase();
        if (lower.has(ql)) return lower.get(ql)!;
        const vq = devowel(ql);
        if (vowel.has(vq)) return vowel.get(vq)!;
        return "";
    });
}

Complexity

⏰ Time complexity: O(N + Q * L) — N = wordlist size, Q = queries size, L = word length (≤7).
🧺 Space complexity: O(N * L) — For the hash maps.

Problem#

Examples#

Example 1#

Example 2#

Constraints#

Solution#

Method 1 – Hash Maps and Vowel Masking#

Intuition#

Approach#

Code#

Complexity#