Vowel Spellchecker

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

1. 1Insert every original word into a case-sensitive hash set, because exact matching must distinguish spellings such as KiTe and kite.
2. 2Convert 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.
3. 3Convert 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.
4. 4Process each query by checking the original-word set first, because returning a weaker match before an exact match would violate the required priority.
5. 5If 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.
6. 6If the lowercase lookup fails, check the vowel-mask map and return its stored first word, because this is the final allowed form of matching.
7. 7If 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

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

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

Common mistakesthe priority and tie-breaking rules are easy to flatten