#966 Vowel Spellchecker - Solution

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

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.

The key idea in #966 Vowel Spellchecker is to simulate the spellchecker rules in priority order: exact match, case-insensitive match, and vowel error match. Efficient lookup is achieved using hash tables.

First, store all words in a set to quickly detect exact matches. Next, create a map from the lowercase version of each word to its first occurrence in the word list. This helps resolve case-insensitive queries. Finally, build another hash map where each word is converted to a vowel-normalized form (for example, replacing vowels with a placeholder like *). This structure allows matching queries that differ only by vowel substitutions.

For each query, check the rules sequentially: exact match, lowercase match, then vowel-normalized match. If none exist, return an empty string. With preprocessing and constant-time lookups using hash maps, the solution efficiently handles all queries.

Approach	Time Complexity	Space Complexity
Hash Set + Hash Map with Vowel Normalization	O(W * L + Q * L)	O(W * L)

Solutions (4)

Hash Maps for Different Match Types

This approach uses three types of hash maps:

Exact Match: This stores the words in their original form for exact matching.
Case-Insensitive Map: This converts all words to lowercase for handling capitalization errors and maps them to their original form for case restoration.
Vowel-Insensitive Map: This converts all vowels in words to a placeholder (e.g., '*'), enabling matching words that differ only by vowel substitutions.

For each query, the spellchecker checks in the order of exact matches, case-insensitive matches, and vowel-insensitive matches and returns the first match found.

Time Complexity: O(N + M) per query, where N is the length of the wordlist and M is the length of the longest query.
Space Complexity: O(N), to store the dictionaries for the wordlist.

Python Java

1import java.util.*;
2public class VowelSpellchecker {
3    public String[] spellchecker(String[] wordlist, String[] queries) {
4        Set<String> exactMatches = new HashSet<>(Arrays.asList(wordlist));
5        Map<String, String> caseSensitiveMatches = new HashMap<>();
6        Map<String, String> vowelInsensitiveMatches = new HashMap<>();
7
8        for (int i = wordlist.length - 1; i >= 0; i--) {
9            String word = wordlist[i];
10            String lower = word.toLowerCase();
11            String vowelMask = maskVowels(lower);
12            caseSensitiveMatches.putIfAbsent(lower, word);
13            vowelInsensitiveMatches.putIfAbsent(vowelMask, word);
14        }
15        
16        String[] result = new String[queries.length];
17
18        for (int i = 0; i < queries.length; i++) {
19            String query = queries[i];
20            if (exactMatches.contains(query)) {
21                result[i] = query;
22            } else {
23                String lowerQuery = query.toLowerCase();
24                String maskedQuery = maskVowels(lowerQuery);
25
26                if (caseSensitiveMatches.containsKey(lowerQuery)) {
27                    result[i] = caseSensitiveMatches.get(lowerQuery);
28                } else if (vowelInsensitiveMatches.containsKey(maskedQuery)) {
29                    result[i] = vowelInsensitiveMatches.get(maskedQuery);
30                } else {
31                    result[i] = "";
32                }
33            }
34        }
35        return result;
36    }
37
38    private String maskVowels(String word) {
39        char[] c = word.toCharArray();
40        for (int i = 0; i < c.length; i++) {
41            if ("aeiou".indexOf(c[i]) >= 0) {
42                c[i] = '*';
43            }
44        }
45        return new String(c);
46    }
47}

Explanation

This Java solution uses a similar logic to the Python implementation. It keeps track of potential matches using three collections: a set for exact matches, a map for case-insensitive matches, and another map for vowel-insensitive matches. The method maskVowels is used to transform words so vowels are replaced with a placeholder, facilitating vowel-error detection.

Trie with Search Functions for Different Match Types

This approach utilizes a trie data structure to accommodate the various search conditions:

Exact Match: Regular trie for exact word representation.
Case-Insensitive Match: Insert both the lowercase and original version in the trie and search in case-insensitive fashion.
Vowel-Insensitive Match: Insert words into the trie after transforming their vowels to a common character, like '*'.

For each query, iterate through trie searches, trying to find matches in the priority of exact matches, case-insensitive matches, and vowel-insensitive matches.

Time Complexity: O(N + M) per query, where N is the length of the wordlist and M is the length of the longest query.
Space Complexity: O(N), for storing each transformed mapping in the maps used.

C++JavaScript

1#include <unordered_map>
2#include <unordered_set>
3#include <vector>
#include <string>
#include <algorithm>
using namespace std;
class Spellchecker {
public:
    vector<string> spellchecker(vector<string>& wordlist, vector<string>& queries) {
        unordered_set<string> exactMatch(wordlist.begin(), wordlist.end());
        unordered_map<string, string> caseInsensitiveMap;
        unordered_map<string, string> vowelInsensitiveMap;

        for (auto it = wordlist.rbegin(); it != wordlist.rend(); ++it) {
            string lowerWord = toLower(*it);
            caseInsensitiveMap[lowerWord] = *it;
            vowelInsensitiveMap[maskVowels(lowerWord)] = *it;
        }

        vector<string> results;
        for (const string& query : queries) {
            if (exactMatch.count(query)) {
                results.push_back(query);
            } else {
                string lowerQuery = toLower(query);
                string vowelMaskedQuery = maskVowels(lowerQuery);
                if (caseInsensitiveMap.count(lowerQuery)) {
                    results.push_back(caseInsensitiveMap[lowerQuery]);
                } else if (vowelInsensitiveMap.count(vowelMaskedQuery)) {
                    results.push_back(vowelInsensitiveMap[vowelMaskedQuery]);
                } else {
                    results.push_back("");
                }
            }
        }
        return results;
    }

private:
    string toLower(const string& word) {
        string res = word;
        transform(res.begin(), res.end(), res.begin(), ::tolower);
        return res;
    }

    string maskVowels(string word) {
        for (char& c : word) {
            if (isVowel(c)) c = '*';
        }
        return word;
    }

    bool isVowel(char c) {
        return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
    }
};