966. Vowel Spellchecker

Problem 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 word in the wordlist.
• 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.

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.

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

Constraints:

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

Python Solution

class Solution:
    def spellchecker(self, wordlist: List[str], queries: List[str]) -> List[str]:
        def devowel(word: str) -> str:
            return ''.join('*' if c in 'aeiou' else c.lower() for c in word)
        
        words_perfect = set(wordlist)
        words_cap = {}
        words_vow = {}
        
        for word in wordlist:
            wordlow = word.lower()
            words_cap[wordlow] = word
            words_vow[devowel(wordlow)] = word
        
        def solve(query: str) -> str:
            if query in words_perfect:
                return query
                
            queryL = query.lower()
            if queryL in words_cap:
                return words_cap[queryL]
                
            queryLV = devowel(queryL)
            if queryLV in words_vow:
                return words_vow[queryLV]
                
            return ""
        
        return [solve(query) for query in queries]

Java Solution

class Solution {
    public String[] spellchecker(String[] wordlist, String[] queries) {
        Set wordsPerfect = new HashSet<>();
        Map wordsCap = new HashMap<>();
        Map wordsVow = new HashMap<>();
        
        for (String word : wordlist) {
            wordsPerfect.add(word);
            
            String wordlow = word.toLowerCase();
            wordsCap.putIfAbsent(wordlow, word);
            
            String wordlowDV = devowel(wordlow);
            wordsVow.putIfAbsent(wordlowDV, word);
        }
        
        String[] ans = new String[queries.length];
        int t = 0;
        for (String query : queries) {
            ans[t++] = solve(query, wordsPerfect, wordsCap, wordsVow);
        }
        return ans;
    }
    
    private String solve(String query, Set wordsPerfect,
                        Map wordsCap, Map wordsVow) {
        if (wordsPerfect.contains(query)) {
            return query;
        }
        
        String queryL = query.toLowerCase();
        if (wordsCap.containsKey(queryL)) {
            return wordsCap.get(queryL);
        }
        
        String queryLV = devowel(queryL);
        if (wordsVow.containsKey(queryLV)) {
            return wordsVow.get(queryLV);
        }
        
        return "";
    }
    
    private String devowel(String word) {
        StringBuilder ans = new StringBuilder();
        for (char c : word.toCharArray()) {
            ans.append(isVowel(c) ? '*' : c);
        }
        return ans.toString();
    }
    
    private boolean isVowel(char c) {
        return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
    }
}

C++ Solution

class Solution {
public:
    vector spellchecker(vector& wordlist, vector& queries) {
        unordered_set wordsPerfect;
        unordered_map wordsCap;
        unordered_map wordsVow;
        
        for (string word : wordlist) {
            wordsPerfect.insert(word);
            
            string wordlow = word;
            transform(wordlow.begin(), wordlow.end(), wordlow.begin(), ::tolower);
            wordsCap[wordlow] = word;
            
            string wordlowDV = devowel(wordlow);
            wordsVow[wordlowDV] = word;
        }
        
        vector ans;
        for (string query : queries) {
            ans.push_back(solve(query, wordsPerfect, wordsCap, wordsVow));
        }
        return ans;
    }
    
private:
    string solve(string query, unordered_set& wordsPerfect,
                unordered_map& wordsCap,
                unordered_map& wordsVow) {
        if (wordsPerfect.count(query)) {
            return query;
        }
        
        string queryL = query;
        transform(queryL.begin(), queryL.end(), queryL.begin(), ::tolower);
        if (wordsCap.count(queryL)) {
            return wordsCap[queryL];
        }
        
        string queryLV = devowel(queryL);
        if (wordsVow.count(queryLV)) {
            return wordsVow[queryLV];
        }
        
        return "";
    }
    
    string devowel(string word) {
        string ans;
        for (char c : word) {
            ans += isVowel(c) ? '*' : c;
        }
        return ans;
    }
    
    bool isVowel(char c) {
        return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
    }
};

JavaScript Solution

/**
 * @param {string[]} wordlist
 * @param {string[]} queries
 * @return {string[]}
 */
var spellchecker = function(wordlist, queries) {
    const wordsPerfect = new Set(wordlist);
    const wordsCap = new Map();
    const wordsVow = new Map();
    
    for (const word of wordlist) {
        const wordlow = word.toLowerCase();
        if (!wordsCap.has(wordlow)) {
            wordsCap.set(wordlow, word);
        }
        
        const wordlowDV = devowel(wordlow);
        if (!wordsVow.has(wordlowDV)) {
            wordsVow.set(wordlowDV, word);
        }
    }
    
    function solve(query) {
        if (wordsPerfect.has(query)) {
            return query;
        }
        
        const queryL = query.toLowerCase();
        if (wordsCap.has(queryL)) {
            return wordsCap.get(queryL);
        }
        
        const queryLV = devowel(queryL);
        if (wordsVow.has(queryLV)) {
            return wordsVow.get(queryLV);
        }
        
        return "";
    }
    
    function devowel(word) {
        return word.replace(/[aeiou]/g, '*');
    }
    
    return queries.map(solve);
};

C# Solution

public class Solution {
    public string[] Spellchecker(string[] wordlist, string[] queries) {
        var wordsPerfect = new HashSet(wordlist);
        var wordsCap = new Dictionary();
        var wordsVow = new Dictionary();
        
        foreach (string word in wordlist) {
            string wordlow = word.ToLower();
            if (!wordsCap.ContainsKey(wordlow)) {
                wordsCap[wordlow] = word;
            }
            
            string wordlowDV = Devowel(wordlow);
            if (!wordsVow.ContainsKey(wordlowDV)) {
                wordsVow[wordlowDV] = word;
            }
        }
        
        return queries.Select(query => Solve(query, wordsPerfect, wordsCap, wordsVow)).ToArray();
    }
    
    private string Solve(string query, HashSet wordsPerfect,
                        Dictionary wordsCap,
                        Dictionary wordsVow) {
        if (wordsPerfect.Contains(query)) {
            return query;
        }
        
        string queryL = query.ToLower();
        if (wordsCap.ContainsKey(queryL)) {
            return wordsCap[queryL];
        }
        
        string queryLV = Devowel(queryL);
        if (wordsVow.ContainsKey(queryLV)) {
            return wordsVow[queryLV];
        }
        
        return "";
    }
    
    private string Devowel(string word) {
        return new string(word.Select(c => "aeiou".Contains(c) ? '*' : c).ToArray());
    }
}