Problem Description

The Vowel Spellchecker problem asks you to implement a spellchecker for a given list of words. You are given two arrays: wordlist (the dictionary of correct words) and queries (words to check/correct). For each query, you must return the first word from wordlist that matches the query according to the following rules, in order of priority:

1. Exact match: If the query matches a word in wordlist exactly (including case), return that word.
2. Case-insensitive match: If the query matches a word in wordlist case-insensitively, return the first such word.
3. Vowel error match: If the query matches a word in wordlist after replacing all vowels (a, e, i, o, u) with any vowel (case-insensitive), return the first such word.
4. If no match is found, return an empty string "".

Each query is processed independently, and you must not reuse elements for different queries. The result is an array of strings where each element is the answer for the corresponding query.

Thought Process

The problem asks us to check for matches in a specific order: exact, case-insensitive, then vowel error. A brute-force approach would be to check each query against every word in wordlist for all three rules, but this would be inefficient, especially for large lists.

• First, we want to make lookups efficient. For that, we can use hash maps (dictionaries) to store words in different "normalized" forms.
• For case-insensitive and vowel error matches, we need to transform both the wordlist and the queries in the same way, so that lookups are fast and easy.
• By preprocessing wordlist into several maps, we can answer each query in constant time for each rule.
• The conceptual shift is from direct comparison to normalization and mapping, trading a bit of preprocessing for much faster query checks.

Solution Approach

Let's break down the approach step by step:

1. Preprocessing:
   • Create a set of all words in wordlist for exact matches.
   • Create a dictionary mapping each lowercase word to its first occurrence in wordlist for case-insensitive matches.
   • Create a dictionary mapping each "vowel-masked" word (all vowels replaced with '*') to its first occurrence in wordlist for vowel error matches.
2. Normalization Functions:
   • Define a function to lowercase a word.
   • Define a function to replace all vowels in a word with '*' (vowel masking), ignoring case.
3. Processing Queries:
   • For each query, check for an exact match in the set.
   • If not found, check for a case-insensitive match in the lowercase map.
   • If still not found, check for a vowel error match in the vowel-masked map.
   • If none match, return an empty string.
4. Return: Build and return the result list, one answer per query.

We use hash maps for O(1) average lookup time. This ensures that after the initial preprocessing, each query is handled very efficiently.

Example Walkthrough

Let's walk through an example:

    wordlist = ["KiTe", "kite", "hare", "Hare"]
    queries = ["kite", "Kite", "KiTe", "Hare", "HARE", "Hear", "hear", "keti", "keet", "keto"]
  

1. Preprocessing:
   • Exact words: {"KiTe", "kite", "hare", "Hare"}
   • Case-insensitive map:
     • "kite" → "KiTe"
     • "hare" → "hare"
   • Vowel-masked map:
     • "k*t*" → "KiTe"
     • "h*r*" → "hare"
2. Queries:
   • "kite": exact match ("kite") → "kite"
   • "Kite": case-insensitive match ("kite") → "KiTe"
   • "KiTe": exact match ("KiTe") → "KiTe"
   • "Hare": exact match ("Hare") → "Hare"
   • "HARE": case-insensitive match ("hare") → "hare"
   • "Hear": vowel-masked match ("h*r*") → "hare"
   • "hear": vowel-masked match ("h*r*") → "hare"
   • "keti": vowel-masked match ("k*t*") → "KiTe"
   • "keet": vowel-masked match ("k*t*") → "KiTe"
   • "keto": vowel-masked match ("k*t*") → "KiTe"
3. Result:

           ["kite", "KiTe", "KiTe", "Hare", "hare", "hare", "hare", "KiTe", "KiTe", "KiTe"]
         

At each step, we check for matches in the prescribed order and return the first valid match.

Time and Space Complexity

Brute-force approach:

• For each query, compare with every word in wordlist for all three rules.
• If Q is the number of queries and W is the number of words, this is O(Q * W * L), where L is the average word length.

• Preprocessing: O(W * L) time and space to build the maps.
• For each query, O(1) average time for each lookup, so total O(Q * L) time.
• Overall: O(W * L + Q * L) time and O(W * L) space.
• This is much faster and more scalable for large inputs.

Summary

The Vowel Spellchecker problem demonstrates the power of preprocessing and normalization for efficient lookup. By mapping words into different forms (lowercase, vowel-masked), we can answer complex matching queries in constant time. The key insight is to trade a bit of upfront work for fast, repeated query handling. This approach is both elegant and practical, making it a strong pattern for similar problems involving fuzzy matching or normalization.

Code Implementation

class Solution:
    def spellchecker(self, wordlist, queries):
        def devowel(word):
            return ''.join('*' if c.lower() in 'aeiou' else c.lower() for c in word)
        
        words_exact = set(wordlist)
        words_lower = {}
        words_vowel = {}
        for word in wordlist:
            lower = word.lower()
            vowel = devowel(word)
            if lower not in words_lower:
                words_lower[lower] = word
            if vowel not in words_vowel:
                words_vowel[vowel] = word

        result = []
        for q in queries:
            if q in words_exact:
                result.append(q)
            else:
                lower = q.lower()
                vowel = devowel(q)
                if lower in words_lower:
                    result.append(words_lower[lower])
                elif vowel in words_vowel:
                    result.append(words_vowel[vowel])
                else:
                    result.append("")
        return result
      

class Solution {
public:
    string devowel(const string& word) {
        string res;
        for (char c : word) {
            char l = tolower(c);
            if (l == 'a' || l == 'e' || l == 'i' || l == 'o' || l == 'u')
                res += '*';
            else
                res += l;
        }
        return res;
    }

    vector<string> spellchecker(vector<string>& wordlist, vector<string>& queries) {
        unordered_set<string> words_exact(wordlist.begin(), wordlist.end());
        unordered_map<string, string> words_lower;
        unordered_map<string, string> words_vowel;
        for (const string& word : wordlist) {
            string lower, vowel;
            for (char c : word) lower += tolower(c);
            vowel = devowel(word);
            if (words_lower.find(lower) == words_lower.end()) words_lower[lower] = word;
            if (words_vowel.find(vowel) == words_vowel.end()) words_vowel[vowel] = word;
        }
        vector<string> result;
        for (const string& q : queries) {
            if (words_exact.count(q)) {
                result.push_back(q);
            } else {
                string lower, vowel;
                for (char c : q) lower += tolower(c);
                vowel = devowel(q);
                if (words_lower.count(lower)) {
                    result.push_back(words_lower[lower]);
                } else if (words_vowel.count(vowel)) {
                    result.push_back(words_vowel[vowel]);
                } else {
                    result.push_back("");
                }
            }
        }
        return result;
    }
};
      

class Solution {
    private String devowel(String word) {
        StringBuilder sb = new StringBuilder();
        for (char c : word.toCharArray()) {
            char l = Character.toLowerCase(c);
            if (l == 'a' || l == 'e' || l == 'i' || l == 'o' || l == 'u')
                sb.append('*');
            else
                sb.append(l);
        }
        return sb.toString();
    }

    public String[] spellchecker(String[] wordlist, String[] queries) {
        Set<String> wordsExact = new HashSet<>(Arrays.asList(wordlist));
        Map<String, String> wordsLower = new HashMap<>();
        Map<String, String> wordsVowel = new HashMap<>();
        for (String word : wordlist) {
            String lower = word.toLowerCase();
            String vowel = devowel(word);
            wordsLower.putIfAbsent(lower, word);
            wordsVowel.putIfAbsent(vowel, word);
        }
        String[] result = new String[queries.length];
        for (int i = 0; i < queries.length; ++i) {
            String q = queries[i];
            if (wordsExact.contains(q)) {
                result[i] = q;
            } else {
                String lower = q.toLowerCase();
                String vowel = devowel(q);
                if (wordsLower.containsKey(lower)) {
                    result[i] = wordsLower.get(lower);
                } else if (wordsVowel.containsKey(vowel)) {
                    result[i] = wordsVowel.get(vowel);
                } else {
                    result[i] = "";
                }
            }
        }
        return result;
    }
}
      

var spellchecker = function(wordlist, queries) {
    const devowel = (word) => word.toLowerCase().replace(/[aeiou]/g, '*');
    const wordsExact = new Set(wordlist);
    const wordsLower = new Map();
    const wordsVowel = new Map();
    for (const word of wordlist) {
        const lower = word.toLowerCase();
        const vowel = devowel(word);
        if (!wordsLower.has(lower)) wordsLower.set(lower, word);
        if (!wordsVowel.has(vowel)) wordsVowel.set(vowel, word);
    }
    const result = [];
    for (const q of queries) {
        if (wordsExact.has(q)) {
            result.push(q);
        } else {
            const lower = q.toLowerCase();
            const vowel = devowel(q);
            if (wordsLower.has(lower)) {
                result.push(wordsLower.get(lower));
            } else if (wordsVowel.has(vowel)) {
                result.push(wordsVowel.get(vowel));
            } else {
                result.push("");
            }
        }
    }
    return result;
};