Vowel Spellchecker — Editorial

Opening the reading…

Intuitioneach rule becomes a different lookup key

The rules are ordered, so a query must not be treated as having just one kind of identity. Its original spelling matters first, its lowercase spelling matters second, and its spelling with every vowel replaced by one common marker matters third. Each identity can be computed as a string and used as a key in a hash-based container.

While reading wordlist from left to right, save the first word for each lowercase key and each vowel-mask key. The first word is important because the problem asks for the first matching word, not an arbitrary one. For every query, test the three keys in rule order and stop at the first successful lookup.

Approachbuild one table for each level of forgiveness

Insert every original word into a case-sensitive hash set, because exact matching must distinguish spellings such as KiTe and kite.

Convert each word to lowercase and store the first word under that lowercase key, because later words with the same key must not replace the earliest match.

Convert each word to lowercase again while replacing every a, e, i, o, and u with the same marker, then store the first word under this vowel-mask key so different vowels become interchangeable.

Process each query by checking the original-word set first, because returning a weaker match before an exact match would violate the required priority.

If the exact lookup fails, check the lowercase map and return its stored original spelling, because case-insensitive matching still returns the word as it appeared in wordlist.

If the lowercase lookup fails, check the vowel-mask map and return its stored first word, because this is the final allowed form of matching.

If all three lookups fail, append an empty string, because no permitted interpretation of the query matches a word.

Complexityhash lookups are expected constant time per character-normalized key

MEASURE	BOUND	WHY
Time	O((W + Q) x L) expected	Each word is copied and examined a constant number of times to build its keys, and each query is examined the same way before a constant number of expected hash lookups. Hash collisions can make an individual lookup slower; in the worst collision-heavy shape, the hash operations can degrade toward linear work in the number of stored keys.
Space	O(W x L) extra	The set and two maps store up to a constant number of normalized or original strings for each word, and each stored string has length at most L. The returned answer array is required output and is excluded from the extra-space bound. The bound is still O(W x L) when many words have distinct keys; duplicate keys only reduce actual storage.

W is the number of words, Q is the number of queries, and L is the maximum word or query length.

Annotated solutionC++ - hash tables with first-match preservation

CPPBuild exact, lowercase, and vowel-mask tables, then test each query in priority order.

#include <algorithm>
#include <cctype>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>

using namespace std;

class Solution {
private:
    static string toLower(const string& s) {
        string result = s;
        for (char& c : result) {
            c = static_cast<char>(tolower(static_cast<unsigned char>(c)));
        }
        return result;
    }

    static string vowelMask(const string& s) {
        string result;
        result.reserve(s.size());

        for (char c : s) {
            char lower = static_cast<char>(tolower(static_cast<unsigned char>(c)));
            if (lower == 'a' || lower == 'e' || lower == 'i' ||
                lower == 'o' || lower == 'u') {
                result.push_back('*');
            } else {
                result.push_back(lower);
            }
        }
        return result;
    }

public:
    vector<string> spellchecker(vector<string>& wordlist, vector<string>& queries) {
        unordered_set<string> originalWords;
        unordered_map<string, string> lowercaseWords;
        unordered_map<string, string> vowelWords;

        for (const string& word : wordlist) {
            originalWords.insert(word);

            string lower = toLower(word);
            if (!lowercaseWords.count(lower)) {
                lowercaseWords[lower] = word;
            }

            string mask = vowelMask(word);
            if (!vowelWords.count(mask)) {
                vowelWords[mask] = word;
            }
        }

        vector<string> answer;
        answer.reserve(queries.size());

        for (const string& query : queries) {
            if (originalWords.count(query)) {
                answer.push_back(query);
                continue;
            }

            string lower = toLower(query);
            if (lowercaseWords.count(lower)) {
                answer.push_back(lowercaseWords[lower]);
                continue;
            }

            string mask = vowelMask(query);
            if (vowelWords.count(mask)) {
                answer.push_back(vowelWords[mask]);
                continue;
            }

            answer.push_back("");
        }

        return answer;
    }
};

The two if checks used while building the maps are the part that preserves the statement's tie-breaking rule. A map assignment would be correct for deciding whether a key exists, but assigning every time would replace an earlier word with a later one. Keeping only the first insertion makes the lookup result independent of any later duplicate.