Problem Explanation:

The given problem is a spellchecking problem where you are provided with a list of correct "wordlist" words and a list of "queries" that may contain mistakes. The spellchecker is designed to correct two types of errors. The first error occurs when the case of the word does not match the correct word in the "wordlist" and the second error occurs when the vowels in the "query" word are incorrectly used.

It should be noted that if the "query" word is an exact match (including case) in the "wordlist", the same word should be returned. If there is no match based on capitalization or vowel errors, an empty string should be returned.

To demonstrate: Let's assume wordlist = ["KiTe","kite","hare","Hare"] and queries = ["kite","Kite","KiTe","Hare","HARE","Hear","hear","keti","keet","keto"]. The spellchecker will return ["kite","KiTe","KiTe","Hare","hare","","","KiTe","","KiTe"], correcting the capitalization and vowel errors, and returning empty string for words with no match.

Approach:

The proposed solution uses three dictionaries to categorize all words into three categories: as is, lower case and vowel free. For each query, the solution first checks if the word matches with the "as is" category, then lower case category and then vowel free category. If no match is found, it returns an empty string.

Python Solution:

1
2python
3import collections
4
5class Solution:
6    def spellchecker(self, wordlist, queries):
7        wordset = set(wordlist)
8        def todev(word):
9            return "".join('*' if c in 'aeiou' else c for c in word.lower())
10        words = collections.defaultdict(list)
11        wordssemivow = collections.defaultdict(list)
12        for word in wordlist[::-1]:
13            words[word.lower()].append(word)
14            wordssemivow[todev(word)].append(word)
15        def solve(word):
16            if word in wordset: return word
17            lword = word.lower()
18            if lword in words:
19                return words[lword][0]
20            devow = todev(word)
21            if devow in wordssemivow:
22                return wordssemivow[devow][0]
23            return ""   
24        return map(solve, queries)

Java Solution:

1
2java
3class Solution {
4    public String[] spellchecker(String[] wordlist, String[] queries) {
5        Map<String, String> wordDict = new HashMap<>();
6        Map<String, String> capDict = new HashMap<>();
7        Map<String, String> vowDict = new HashMap<>();
8        
9        for (String word : wordlist) {
10            String lowWord = word.toLowerCase();
11            String vowWord = lowWord.replaceAll("[aeiou]", "*");
12            wordDict.putIfAbsent(word, word);
13            capDict.putIfAbsent(lowWord, word);
14            vowDict.putIfAbsent(vowWord, word);
15        }
16        
17        int n = queries.length;
18        String[] ans = new String[n];
19        for (int i = 0; i < n; i++) {
20            String query = queries[i];
21            String lowQuery = query.toLowerCase();
22            String vowQuery = lowQuery.replaceAll("[aeiou]", "*");
23            
24            if (wordDict.containsKey(query)) {
25                ans[i] = wordDict.get(query);
26            } else if (capDict.containsKey(lowQuery)) {
27                ans[i] = capDict.get(lowQuery);
28            } else {
29                ans[i] = vowDict.getOrDefault(vowQuery, "");
30            }
31        }
32        return ans;
33    }
34}

Javascript Solution:

1
2javascript
3var spellchecker = function(wordlist, queries) {
4    const map = {};
5    const capMap = {};
6    const vowMap = {};
7    const ans = [];
8    
9    const check = (key, def) => map[key] || capMap[key.toLowerCase()] || vowMap[key.toLowerCase().replace(/[aeiou]/g, '*')] || def;
10    
11    for (let i = wordlist.length -1; i >=0; i--) {
12        map[wordlist[i]] = wordlist[i];
13        capMap[wordlist[i].toLowerCase()] = wordlist[i];
14        vowMap[wordlist[i].toLowerCase().replace(/[aeiou]/g, '*')] = wordlist[i];
15    }
16    for (let i = 0; i < queries.length; i ++) {
17        ans.push(check(queries[i], ""));
18    }
19    return ans;
20};

C++ Solution:

1
2cpp
3class Solution {
4public:
5    vector<string> spellchecker(vector<string>& wordlist, vector<string>& queries) {
6        unordered_set<string> words(wordlist.begin(), wordlist.end());
7        unordered_map<string, string> map, vowels;
8        for (string w : wordlist) {
9            string lower = "", vowel = "";
10            for (char c : w) {
11                lower += tolower(c);
12                vowel += string("aeiou").find(tolower(c)) != string::npos ? '*' : tolower(c);
13            }
14            map.insert({lower, w});
15            vowels.insert({vowel, w});
16        }
17        for (auto &query : queries) {
18            if (!words.count(query)) {
19                string lower = "", vowel = "";
20                for (char c : query) {
21                    lower += tolower(c);
22                    vowel += string("aeiou").find(tolower(c)) != string::npos ? '*' : tolower(c);
23                }
24                if (map.count(lower)) query = map[lower];
25                else if (vowels.count(vowel)) query = vowels[vowel];
26                else query = "";
27            }
28        }
29        return queries;
30    }
31};

C# Solution:

1
2csharp
3public class Solution {
4    public string[] Spellchecker(string[] wordlist, string[] queries) {
5        var ans = new string[queries.Length];
6        
7        var exact = new Dictionary<string, string>();
8        var ignoreCase = new Dictionary<string, string>();
9        var ignoreVowels = new Dictionary<string, string>();
10        
11        foreach(var word in wordlist){
12            var lower = word.ToLower();
13            var devowel = lower.Replace("a","*")
14                              .Replace("e","*")
15                              .Replace("i","*")
16                              .Replace("o","*")
17                              .Replace("u","*");
18            
19            exact[word] = word;
20            if(!ignoreCase.ContainsKey(lower)){
21                ignoreCase[lower] = word;
22            }
23            if(!ignoreVowels.ContainsKey(devowel)){
24                ignoreVowels[devowel] = word;
25            }
26        }
27        for(int i = 0; i < queries.Length; i++){
28            var lowerQuery = queries[i].ToLower();
29            var devowelQuery = lowerQuery.Replace("a","*")
30                                          .Replace("e","*")
31                                          .Replace("i","*")
32                                          .Replace("o","*")
33                                          .Replace("u","*");
34            
35            if(exact.ContainsKey(queries[i])){
36                ans[i] = exact[queries[i]];
37            }else if(ignoreCase.ContainsKey(lowerQuery)){
38                ans[i] = ignoreCase[lowerQuery];
39            }else if(ignoreVowels.ContainsKey(devowelQuery)){
40                ans[i] = ignoreVowels[devowelQuery];
41            }else{
42                ans[i] = "";
43            }
44        }
45        return ans;
46    }
47}

So, this solution uses three different dictionaries, each for a different scenario. It first checks the original word, then the word in lowercase, and finally the word devoid of vowels. In each dictionary, if the query is found, it returns the word stored in the dictionary against the corresponding 'key'. If not, it returns an empty string. It is a handy solution for correcting common spelling mistakes.In the Python solution, we're creating a set of the words in our wordlist for rapid access. We're also creating dictionaries that map lowercased and devoweled versions of the words to their original counterparts. For every query, we first check if it's already in the word set. If it is, we return it as it is. If it's not, we check if a lowercased version of the query can be found in our words dictionary. If that also fails, we check if a devoweled version of the query exists in our devoweled words dictionary. The defaultdict type is used to ensure that an empty list is returned when a key is not in the dictionary.

The Java solution takes a similar approach, where we're also creating three separate dictionaries. The Java solution uses putIfAbsent method to ensure no overwriting occurs. Then a linear scan on the queries array is performed to see if the word exists in an 'as is' form, lowercase or devoweled. Based on the match, the corresponding word is added to the answer string array.

The JavaScript solution uses a similar approach of creating dictionaries for original, lowercased, and devoweled words in a loop that iterates in reverse to make sure the first encounter is saved last and thus returned first. "String.prototype.replace()" function is used here to swap out vowels with a 'star' to create the devoweled version. On the queries, the check function looks up first in the original dictionary, then in lowercase and finally in the devoweled one. If there's no match, it returns an empty string.

In the C++ solution, unordered_map and unordered_set are used to take advantage of their constant time complexity for search queries, combined with the use of tolower() function for case-insensitive comparison, and a string of '*' characters for vowel insensitive comparison.

The C# Solution follows the same principle, creating dictionaries to hold the words found in the wordlist in their original form, lower case form and form devoid of vowels. String.Replace() is used to replace each vowel with an asterisk '*' character to handle vowel insensitive comparison. For each query, it checks these dictionaries in order and assigns the respective match or an empty string if none is found to the answer array.

In conclusion, all of them are pretty efficient solutions taking advantage of the speed of search in a set, or hash-maps/dictionaries, and cleverly handling 3 different scenarios for each word.