Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

Matching has three priorities: exact spelling, case-insensitive spelling, then case-insensitive vowel substitution. A separate lookup for each rule preserves that priority, while recording only the first word for a normalized key enforces the word-list tie rule.

Approach

Build an exact-word set, a lowercase-word map, and a map whose lowercase keys replace every vowel with *. Never overwrite an existing normalized mapping. For each query, try the exact set first, then its lowercase key, then its vowel-masked key. Return the first matching original word or an empty string. Masking each vowel individually preserves word length and consonant positions; it does not allow inserting or removing characters.

class Solution:
    def spellchecker(self, wordlist: List[str], queries: List[str]) -> List[str]:
        perfect = set()
        cap = {} # key: lower, value: original word
        vow = {} # key: lower and * for every vowel, value: original word

        for w in wordlist:
            perfect.add(w)
            l = w.lower()
            if not l in cap:
                cap[l] = w
            p = "".join('*' if c in 'aeiou' else c for c in l)
            if not p in vow:
                vow[p] = w

        res = []
        for q in queries:
            if q in perfect:
                res.append(q)
                continue
            l = q.lower()
            if l in cap:
                res.append(cap[l])
                continue
            p = "".join('*' if c in 'aeiou' else c for c in l)
            if p in vow:
                res.append(vow[p])
                continue
            res.append('')

        return res

Complexity analysis

Let W be the total characters in wordlist and Q the total characters in all queries. Normalization and hash lookups take O(W + Q) expected time. Auxiliary space is O(W) for preprocessing sets/maps, excluding the returned query answers.