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"]
 
Note:

1 <= wordlist.length <= 5000
1 <= queries.length <= 5000
1 <= wordlist[i].length <= 7
1 <= queries[i].length <= 7
All strings in wordlist and queries consist only of english letters.

Difficulty: interview

Starter code:

class Solution:
    def spellchecker(self, wordlist: List[str], queries: List[str]) -> List[str]:
        

Solutions:
class Solution:
    def spellchecker(self, wordlist: List[str], queries: List[str]) -> List[str]:
        original = set(wordlist)
        insensitive = {w.lower(): w for w in reversed(wordlist)}
        vowels = {}
        for c in reversed(wordlist):
            w = c.lower()
            t = w.replace('a', '_').replace('e', '_').replace('i', '_').replace('o', '_').replace('u', '_')
            vowels[t] = c
        results = []
        for q in queries:
            if q in original:
                results.append(q)
                continue
            low = q.lower()
            if low in insensitive:
                results.append(insensitive[low])
                continue
            # vowel replace
            t = low.replace('a', '_').replace('e', '_').replace('i', '_').replace('o', '_').replace('u', '_')
            if t in vowels:
                results.append(vowels[t])
                continue
            results.append(\"\")
        return results

def match(query, wordsSet):
    if query in wordsSet:
        return True, query
    return False, \"\"

def capitalization(query, lowerWordsSet):
    if query.lower() in lowerWordsSet:
        return True, lowerWordsSet[query.lower()]
    return False, \"\"

def vowelErrors(query, lowerAndWithoutVowelsSet):
    vowelsRemoved = query.lower().replace('a', '*').replace('e', '*').replace('i', '*').replace('o', '*').replace('u', '*')
    if vowelsRemoved in lowerAndWithoutVowelsSet:
        return True, lowerAndWithoutVowelsSet[vowelsRemoved]
    return False,  \"\"          


class Solution:
    def spellchecker(self, wordlist: List[str], queries: List[str]) -> List[str]:
        answer = []
        wordsSet = set(wordlist)
        lowerWordsList = {}
        lowerAndWithoutVowelsSet = {}
        for word in wordlist:
            lowerWordsList.setdefault(word.lower(), word)
            vowelsRemoved = word.lower().replace('a', '*').replace('e', '*').replace('i', '*').replace('o', '*').replace('u', '*')
            lowerAndWithoutVowelsSet.setdefault(vowelsRemoved, word)
        
        for i, query in enumerate(queries):
            res, toAdd = match(query, wordsSet)
            if res:
                answer.append(toAdd)
            else:
                res, toAdd = capitalization(query, lowerWordsList)
                if res:
                    answer.append(toAdd)
                else:
                    res, toAdd = vowelErrors(query, lowerAndWithoutVowelsSet)
                    if res:
                        answer.append(toAdd)
                    else:
                        answer.append(\"\")
        return answer



class Trie:
    def __init__(self):        
        self.cache = defaultdict(str)
        self.exacts = defaultdict(str)
        self.novowels = defaultdict(str)
        self.vowels = set('aeiou')
                
    def novo(self, word):
        word = word.lower()
        grp = list(word)
        for i,g in enumerate(grp):
            if g in self.vowels:
                grp[i] = '*'
        out = ''.join(grp)
        return out

    def add(self, word):    
        lowered = word.lower()
        if lowered not in self.cache:
            self.cache[lowered] = word
            
        self.exacts[word] = word

        nvwl = self.novo(word)
        if nvwl not in self.novowels:            
            self.novowels[nvwl] = word
        
        
    def search(self, word):                    
        if word in self.exacts:
            return word
        
        lowered = word.lower()
        if lowered in self.cache:
            return self.cache[lowered]
        
        novowels = self.novo(word)
        if novowels in self.novowels:
            # print(word, novo(word), self.novowels[self.novo(word)])
            return self.novowels[novowels]
        
        
        return \"\"

class Solution:
    def spellchecker(self, wordlist: List[str], queries: List[str]) -> List[str]:
        tree = Trie()
        
        for word in wordlist:
            tree.add(word)
            
        # out = []
        # for q in queries:
        #     res = tree.search(q)                            
        #     out.append(res)
        
        # print(out)
        return [tree.search(q) for q in queries]



class Trie:
    def __init__(self):        
        self.cache = defaultdict(str)
        self.exacts = defaultdict(str)
        self.novowels = defaultdict(str)
        self.vowels = set('aeiou')
                
    def novo(self, word):
        word = word.lower()
        grp = list(word)
        for i,g in enumerate(grp):
            if g in self.vowels:
                grp[i] = '*'
        out = ''.join(grp)
        return out

    def add(self, words):
        for word in words:
            lowered = word.lower()
            if lowered not in self.cache:
                self.cache[lowered] = word

            self.exacts[word] = word

            nvwl = self.novo(word)
            if nvwl not in self.novowels:            
                self.novowels[nvwl] = word
        
        
    def search(self, word):                    
        if word in self.exacts:
            return word
        
        lowered = word.lower()
        if lowered in self.cache:
            return self.cache[lowered]
        
        novowels = self.novo(word)
        if novowels in self.novowels:
            # print(word, novo(word), self.novowels[self.novo(word)])
            return self.novowels[novowels]
        
        
        return \"\"

class Solution:
    def spellchecker(self, wordlist: List[str], queries: List[str]) -> List[str]:
        tree = Trie()
        
        # for word in wordlist:
        tree.add(wordlist)
            
        # out = []
        # for q in queries:
        #     res = tree.search(q)                            
        #     out.append(res)
        
        # print(out)
        return [tree.search(q) for q in queries]

class Trie:
    def __init__(self):        
        self.cache = defaultdict(str)
        self.exacts = defaultdict(str)
        self.novowels = defaultdict(str)
                
    def novo(self, word):
        grp = list(word)
        for i,g in enumerate(grp):
            if g.lower() in 'aeiou':
                grp[i] = '*'
        out = ''.join(grp)
        out = out.lower()
        return out

    def add(self, word):        
        if word.lower() not in self.cache:
            self.cache[word.lower()] = word
            
        self.exacts[word] = word

        nvwl = self.novo(word)
        if nvwl not in self.novowels:            
            self.novowels[nvwl] = word
        
        
    def search(self, word, start=None):
                    
        if word in self.exacts and start is None:
            return word
        lowered = word.lower()
        if lowered in self.cache and start is None:
            return self.cache[lowered]
        novowels = self.novo(word)
        if novowels in self.novowels and start is None:
            # print(word, novo(word), self.novowels[self.novo(word)])
            return self.novowels[novowels]
        
        
        return \"\"

class Solution:
    def spellchecker(self, wordlist: List[str], queries: List[str]) -> List[str]:
        tree = Trie()
        
        for word in wordlist:
            tree.add(word)
            
        out = []
        for q in queries:
            res = tree.search(q)                            
            out.append(res)
        
        # print(out)
        return out

class Solution:
    def spellchecker(self, words, queries):
        def vowels(s):
            return ''.join('*' if c in 'AEIOU' else c for c in s)
        wordset=set(words)
        cap={w.upper():w for w in reversed(words)}
        vow={vowels(w.upper()):w for w in reversed(words)}
        
        ans=[]
        for q in queries:
            if q in wordset:
                ans.append(q)
                continue
            q=q.upper()
            if q in cap:
                ans.append(cap[q])
                continue
            q=vowels(q)
            if q in vow:
                ans.append(vow[q])
                continue
            ans.append('')
        
        return ans

class Trie:
    def __init__(self):        
        self.cache = defaultdict(str)
        self.exacts = defaultdict(str)
        self.novowels = defaultdict(str)
                
    def novo(self, word):
        grp = list(word)
        vowels = set('aeiou')
        for i,g in enumerate(grp):
            if g.lower() in vowels:
                grp[i] = '*'
        out = ''.join(grp)
        out = out.lower()
        return out

    def add(self, word):    
        lowered = word.lower()
        if lowered not in self.cache:
            self.cache[lowered] = word
            
        self.exacts[word] = word

        nvwl = self.novo(word)
        if nvwl not in self.novowels:            
            self.novowels[nvwl] = word
        
        
    def search(self, word):
                    
        if word in self.exacts:
            return word
        
        lowered = word.lower()
        if lowered in self.cache:
            return self.cache[lowered]
        
        novowels = self.novo(word)
        if novowels in self.novowels:
            # print(word, novo(word), self.novowels[self.novo(word)])
            return self.novowels[novowels]
        
        
        return \"\"

class Solution:
    def spellchecker(self, wordlist: List[str], queries: List[str]) -> List[str]:
        tree = Trie()
        
        for word in wordlist:
            tree.add(word)
            
        # out = []
        # for q in queries:
        #     res = tree.search(q)                            
        #     out.append(res)
        
        # print(out)
        return [tree.search(q) for q in queries]

class Trie:
    def __init__(self):        
        self.cache = defaultdict(str)
        self.exacts = defaultdict(str)
        self.novowels = defaultdict(str)
                
    def novo(self, word):
        grp = list(word)
        vowels = set('aeiou')
        for i,g in enumerate(grp):
            if g.lower() in vowels:
                grp[i] = '*'
        out = ''.join(grp)
        out = out.lower()
        return out

    def add(self, word):        
        if word.lower() not in self.cache:
            self.cache[word.lower()] = word
            
        self.exacts[word] = word

        nvwl = self.novo(word)
        if nvwl not in self.novowels:            
            self.novowels[nvwl] = word
        
        
    def search(self, word, start=None):
                    
        if word in self.exacts and start is None:
            return word
        lowered = word.lower()
        if lowered in self.cache and start is None:
            return self.cache[lowered]
        novowels = self.novo(word)
        if novowels in self.novowels and start is None:
            # print(word, novo(word), self.novowels[self.novo(word)])
            return self.novowels[novowels]
        
        
        return \"\"

class Solution:
    def spellchecker(self, wordlist: List[str], queries: List[str]) -> List[str]:
        tree = Trie()
        
        for word in wordlist:
            tree.add(word)
            
        out = []
        for q in queries:
            res = tree.search(q)                            
            out.append(res)
        
        # print(out)
        return out

class Solution:
    def spellchecker(self, wordlist: List[str], queries: List[str]) -> List[str]:
        if len(queries) == 0:
            return []
        Perfect = set(wordlist)
        Upper = {}
        Vowel = {}
        for word in wordlist:
            l = word.lower()
            if l not in Upper:
                Upper[l] = word
            temp = self.help(l)
            if temp not in Vowel:
                Vowel[temp] = word
    
        
        ans = []
        for word in queries:
            t = word.lower()
            temp = self.help(t)
            if word in Perfect:
                ans.append(word)
            elif t in Upper:
                ans.append(Upper[t])
            elif temp in Vowel:
                ans.append(Vowel[temp])
            else:
                ans.append(\"\")
        
        return ans
        
    def help(self, word):
        return \"\".join('*' if c in 'aeiou' else c
                           for c in word)
        

class Trie:
    def __init__(self):        
        self.cache = defaultdict(str)
        self.exacts = defaultdict(str)
        self.novowels = defaultdict(str)
                
    def novo(self, word):
        grp = list(word)
        vowels = set('aeiou')
        for i,g in enumerate(grp):
            if g.lower() in vowels:
                grp[i] = '*'
        out = ''.join(grp)
        out = out.lower()
        return out

    def add(self, word):        
        if word.lower() not in self.cache:
            self.cache[word.lower()] = word
            
        self.exacts[word] = word

        nvwl = self.novo(word)
        if nvwl not in self.novowels:            
            self.novowels[nvwl] = word
        
        
    def search(self, word):
                    
        if word in self.exacts:
            return word
        
        lowered = word.lower()
        if lowered in self.cache:
            return self.cache[lowered]
        
        novowels = self.novo(word)
        if novowels in self.novowels:
            # print(word, novo(word), self.novowels[self.novo(word)])
            return self.novowels[novowels]
        
        
        return \"\"

class Solution:
    def spellchecker(self, wordlist: List[str], queries: List[str]) -> List[str]:
        tree = Trie()
        
        for word in wordlist:
            tree.add(word)
            
        out = []
        for q in queries:
            res = tree.search(q)                            
            out.append(res)
        
        # print(out)
        return out

class Node:
    def __init__(self):
        self.kids = defaultdict(Node)
        self.words = []
class Trie:
    def __init__(self):
        self.head = Node()
        self.cache = defaultdict(str)
        self.exacts = defaultdict(str)
        self.novowels = defaultdict(str)
        self.time = 0
        self.sortkey = {}
                
    def novo(self, word):
        grp = list(word)
        for i,g in enumerate(grp):
            if g.lower() in 'aeiou':
                grp[i] = '*'
            else:
                grp[i] = grp[i].lower()
        return ''.join(grp)

    def add(self, word):
        curr = self.head
        if word.lower() not in self.cache:
            self.cache[word.lower()] = word
            
        self.exacts[word] = word

        nvwl = self.novo(word)
        if nvwl not in self.novowels:            
            self.novowels[nvwl] = word
        
        
    def search(self, word, start=None):
                    
        if word in self.exacts and start is None:
            return word
        lowered = word.lower()
        if lowered in self.cache and start is None:
            return self.cache[lowered]
        novowels = self.novo(word)
        if novowels in self.novowels and start is None:
            # print(word, novo(word), self.novowels[self.novo(word)])
            return self.novowels[novowels]
        
        
        return \"\"

class Solution:
    def spellchecker(self, wordlist: List[str], queries: List[str]) -> List[str]:
        tree = Trie()
        
        for word in wordlist:
            tree.add(word)
            
        out = []
        for q in queries:
            res = tree.search(q)                            
            out.append(res)
        
        # print(out)
        return out

class Solution:
    def spellchecker(self, wordlist: List[str], queries: List[str]) -> List[str]:
        def insert(word, trie):
            node = trie
            for letter in word:
                if letter in 'aeouiAEOUI':
                    key = '*'
                else:
                    key = letter.lower()
                if not key in node:
                    node[key] = {}
                node = node[key]
            if not '$' in node:
                node['$'] = OrderedDict() 
            node['$'][word] = True
            
        def find(word, trie):
            node = trie
            matched = ''
            for letter in word:
                if letter in 'aeouiAEOUI':
                    key = '*'
                else:
                    key = letter.lower()
                if not key in node:
                    return matched
                node = node[key]
            if '$' in node:
                if word in node['$']:
                    return word
                else:
                    k = 0
                    for word_i in node['$'].keys():
                        if k == 0:
                            matched = word_i
                        if word.lower() == word_i.lower():
                            return word_i
                        k += 1
                    return matched
            else:
                return matched

            
        trie = {}
        for i, word in enumerate(wordlist):
            insert(word, trie)
        ans = []    
        for q in queries:
            ans.append(find(q, trie))
        
        return ans

class Solution:
    def spellchecker(self, wordlist: List[str], queries: List[str]) -> List[str]:
        
        vowel_template = lambda w: w.lower().replace(\"a\", \"#\").replace(\"e\", \"#\").replace(\"i\", \"#\").replace(\"o\", \"#\").replace(\"u\", \"#\")
        
        exact_matches = set(wordlist)
        capital_matches = {w.lower() : w for w in wordlist[::-1]}
        vowel_matches = {vowel_template(w) : w for w in wordlist[::-1]}
        
        
        return [w if w in exact_matches else capital_matches.get(w.lower(), \"\") or vowel_matches.get(vowel_template(w), \"\") for w in queries]

class Solution:    
    def __init__(self):
        self.words = set()
        self.dict_cap = {}
        self.dict_vowel = {}
        
    def _populate_dicts(self, wordlist):
        for word in wordlist:
            self.words.add(word)
            self.dict_cap[word.lower()] = self.dict_cap.setdefault(word.lower(), word)
            self.dict_vowel[self._jokerize_vowels(word.lower())] = self.dict_vowel.setdefault(self._jokerize_vowels(word.lower()), word)
        print(self.dict_vowel)
    
    def _jokerize_vowels(self, word):
        return \"\".join(\"*\" if l.lower() in \"aeiou\" else l for l in word)
    
    def check_word(self, word):
        if word in self.words:
                return word
            
        elif (word := word.lower()) in self.dict_cap:
            return self.dict_cap[word]

        elif (word := self._jokerize_vowels(word)) in self.dict_vowel:
            return self.dict_vowel[word]

        else:
            return \"\"
    
    def spellchecker(self, wordlist: List[str], queries: List[str]) -> List[str]:
        self._populate_dicts(wordlist)

        return [self.check_word(q) for q in queries]

class Solution(object):
    def spellchecker(self, wordlist, queries):
        def devowel(word):
            return \"\".join('*' if c in 'aeiou' else c
                           for c in word)

        words_perfect = set(wordlist)
        words_cap = {}
        words_vow = {}

        for word in wordlist:
            wordlow = word.lower()
            words_cap.setdefault(wordlow, word)
            words_vow.setdefault(devowel(wordlow), word)

        def solve(query):
            if query in words_perfect:
                return query

            queryL = query.lower()
            if queryL in words_cap:
                return words_cap[queryL]

            queryLV = devowel(queryL)
            if queryLV in words_vow:
                return words_vow[queryLV]
            return \"\"

        return map(solve, queries)

class Trie:
    def __init__(self):        
        self.cache = defaultdict(str)
        self.exacts = defaultdict(str)
        self.novowels = defaultdict(str)
                
    def novo(self, word):
        grp = list(word)
        for i,g in enumerate(grp):
            if g.lower() in set('aeiou'):
                grp[i] = '*'
        out = ''.join(grp)
        out = out.lower()
        return out

    def add(self, word):        
        if word.lower() not in self.cache:
            self.cache[word.lower()] = word
            
        self.exacts[word] = word

        nvwl = self.novo(word)
        if nvwl not in self.novowels:            
            self.novowels[nvwl] = word
        
        
    def search(self, word, start=None):
                    
        if word in self.exacts and start is None:
            return word
        lowered = word.lower()
        if lowered in self.cache and start is None:
            return self.cache[lowered]
        novowels = self.novo(word)
        if novowels in self.novowels and start is None:
            # print(word, novo(word), self.novowels[self.novo(word)])
            return self.novowels[novowels]
        
        
        return \"\"

class Solution:
    def spellchecker(self, wordlist: List[str], queries: List[str]) -> List[str]:
        tree = Trie()
        
        for word in wordlist:
            tree.add(word)
            
        out = []
        for q in queries:
            res = tree.search(q)                            
            out.append(res)
        
        # print(out)
        return out

class Solution:
    def spellchecker(self, wordlist: List[str], queries: List[str]) -> List[str]:
        def canonicalize(word: str) -> str:
            chars = list(word.lower())
            for i in range(len(chars)):
                if chars[i] in ['a', 'e', 'i', 'o', 'u']:
                    chars[i] = '.'

            return ''.join(chars)

        def remove_vowel(word: str) -> str:
            chars = list(word)
            for i in range(len(chars)):
                if chars[i] in ['a', 'e', 'i', 'o', 'u']:
                    chars[i] = '.'
                    
            return ''.join(chars)
            
        lowercase_wordlist = {}
        for i in range(len(wordlist)-1, -1, -1):
            word = wordlist[i]
            lowercase_wordlist[word.lower()] = i
            
        antivowel = {}
        for i in range(len(wordlist)-1, -1, -1):
            word = remove_vowel(wordlist[i].lower())
            antivowel[word] = i
        
        # canonical_wordlist = [canonicalize(word) for word in wordlist]
        # print(canonical_wordlist)
        wordlist_lookup = {}
        for i in range(len(wordlist)-1, -1, -1):
            wordlist_lookup[wordlist[i]] = i

        def solve(query):
            #canonical_query = canonicalize(query)
            if query in wordlist_lookup:
                return query
            elif query.lower() in lowercase_wordlist:
                return wordlist[lowercase_wordlist[query.lower()]]
            elif remove_vowel(query.lower()) in antivowel:
                return wordlist[antivowel[remove_vowel(query.lower())]]
            else:
                return \"\"
        
        return [solve(query) for query in queries]


class Solution:
    def spellchecker(self, wordlist: List[str], queries: List[str]) -> List[str]:

        def wild_key(word):
            return \"\".join([\"*\" if c in vowels else c for c in word])
        
        vowels = {'a', 'e', 'i', 'o', 'u'}
        hs_word = set(); hs_lower = defaultdict(); hs_wild = defaultdict()
        for word in wordlist:
            hs_word.add(word)
            
            low_word = word.lower()
            if low_word not in hs_lower: hs_lower[low_word] = word
            
            wild_word = wild_key(low_word)
            if wild_word not in hs_wild: hs_wild[wild_word] = word
        
        res = []
        for query in queries:
            low_query  = query.lower()
            wild_query = wild_key(low_query)
            
            if   query      in hs_word : res.append(query)
            elif low_query  in hs_lower: res.append(hs_lower[low_query ])
            elif wild_query in hs_wild : res.append(hs_wild [wild_query])
            else                       : res.append(\"\")
        return res
\"\"\"
- problem
  * return word list, res[i]: correct word for query = queries[i]

- constraints & notes
  * n: len(wordlist)  , len(queries)   ; 1 <= n <= 5000
  * m: len(wordlist[i], len(queries[i]); 1 <= m <= 7
  * english letters

- solution
  * algorithm
    - 
    - 
    - precedence rules
      * query: exactly match -> return same word
      * query: matches w/ a workd up to capitalization, first such match in wordlist
      * query: matches w/ vowel error, return first match
      * no match: empty
    - helper
      * check capitalization
        - hash table: all wordlist
          hash table {\"k*t*\": [\"KiTe\", \"kite\" -> ordered with same order w/ wordlist]}
          query     : kite w/ k*t*
          * find if query in hash table
            - return first such match
      * check vowel error 
        * 
    
\"\"\"        

class Solution:
    def spellchecker(self, wordlist: List[str], queries: List[str]) -> List[str]:
        st, cap, vow = set(wordlist), {}, {}
        for w in wordlist:
            newC = w.lower()
            newW = \"\".join(c if c not in \"aeiou\" else \"*\" for c in newC)
            if newC not in cap:
                cap[newC] = w
            if newW not in vow:
                vow[newW] = w
        for i, w in enumerate(queries):
            if w in st:
                continue
            elif w.lower() in cap:
                queries[i] = cap[w.lower()]
            else:
                new = \"\".join(c if c not in \"aeiou\" else \"*\" for c in w.lower())
                if new in vow:
                    queries[i] = vow[new]
                else:
                    queries[i] = \"\"
        return queries
        

class Solution:
    def spellchecker(self, wordlist: List[str], queries: List[str]) -> List[str]:
        cache = {}
        words = set()
        vowels = set(['a', 'e', 'i', 'o', 'u'])
        for w in wordlist:
            words.add(w)
            
            if w not in cache:
                cache[w] = w
                
            lowercase = w.lower()
            if lowercase not in cache:
                cache[lowercase] = w
                
            imd_w = lowercase
            for i, ch in enumerate(w):
                if ch.lower() in vowels:
                    imd_w = imd_w[:i] + '*' + imd_w[i + 1:]
            if imd_w not in cache:
                cache[imd_w] = w
            
        # print(cache)
        res = []
        for q in queries:
            # print(q)
            if q in words:
                res.append(q)
            else:
                lowercase = q.lower()
                if lowercase in cache:
                    res.append(cache[lowercase])
                else:
                    imd_w = lowercase
                    for i, ch in enumerate(q):
                        if ch.lower() in vowels:
                            imd_w = imd_w[:i] + '*' + imd_w[i + 1:]
                    # print(imd_w)
                    if imd_w in cache:
                        res.append(cache[imd_w])
                    else:
                        res.append('')
        return res
        # deal with Capitalization issue


class Solution:
    def spellchecker(self, wordlist: List[str], queries: List[str]) -> List[str]:
        words_set=set(wordlist)
        
        vowelLookUp={
            
        }
        lowerLookUp={}
        
        vowels=[\"a\",\"e\",\"i\",\"o\",\"u\"]
        
        for word in wordlist:
            temp=\"\"
            lowercase=word.lower()
            if lowercase not in lowerLookUp:
                lowerLookUp[lowercase]=word
            for i in range(len(lowercase)):
                if lowercase[i] not in vowels:
                    temp+=lowercase[i]
                else:
                    temp+=\"*\"
            if temp not in vowelLookUp:
                vowelLookUp[temp]=word
        
        result=[]
        for query in queries:
            if query in words_set:
                result.append(query)
                continue
            elif query.lower() in lowerLookUp:
                result.append(lowerLookUp[query.lower()])
                continue
            masked_query=\"\"
            query=query.lower()
            for i in range(len(query)):
                if query[i] not in vowels:
                    masked_query+=query[i]
                else:
                    masked_query+=\"*\"
            if masked_query in  vowelLookUp:
                result.append(vowelLookUp[masked_query])
            else:
                result.append(\"\")
        return result
        
        

class Solution:
    def spellchecker(self, wordlist: List[str], queries: List[str]) -> List[str]:
        def devowel(word):
            return \"\".join('*' if c in 'aeiou' else c
                           for c in word)

        words_perfect = set(wordlist)
        words_cap = {}
        words_vow = {}

        for word in wordlist:
            wordlow = word.lower()
            words_cap.setdefault(wordlow, word)
            words_vow.setdefault(devowel(wordlow), word)

        def solve(query):
            if query in words_perfect:
                return query

            queryL = query.lower()
            if queryL in words_cap:
                return words_cap[queryL]

            queryLV = devowel(queryL)
            if queryLV in words_vow:
                return words_vow[queryLV]
            return \"\"

        return map(solve, queries)

class Solution:
    def spellchecker(self, wordlist: List[str], queries: List[str]) -> List[str]:
        wd_raw = set(wordlist)
        wd_low = {}
        wd_vow = {}
        
        for w in wordlist:
            wdLo = w.lower()
            wd_low.setdefault(wdLo, w)
            wd_vow.setdefault(self.devowel(wdLo), w)

        res = []
        
        
        for i,wd in enumerate(queries):
            qLow = wd.lower()
            qVow = self.devowel(qLow)
            
            if wd in wd_raw:
                res.append(wd)
            
            elif qLow in wd_low:
                res.append(wd_low[qLow])
                
            elif qVow in wd_vow:
                res.append(wd_vow[qVow])
                
            else:
                res.append(\"\")
                
        return res
    
    def devowel(self, wd):
        res = []
        for ch in wd:
            if ch in \"aeiou\":
                res.append(\"#\")
            else:
                res.append(ch)
                
        return \"\".join(res)
        
        

class Solution:
    def spellchecker(self, wordlist: List[str], queries: List[str]) -> List[str]:
        exact = {word: word for word in wordlist}
        caps = {word.lower(): word for word in wordlist[::-1]}
        vowel = defaultdict(lambda: '')
        
        _vowels = set('aeiou')
        for word in wordlist[::-1]:
            orig_word, word = word, word.lower()\\
                                        .replace('a', '$')\\
                                        .replace('e', '$')\\
                                        .replace('i', '$')\\
                                        .replace('o', '$')\\
                                        .replace('u', '$')
            vowel[word] = orig_word
                
        ans = deque()
        for query in queries:
            if query in exact:
                ans.append(exact[query])
            elif query.lower() in caps:
                ans.append(caps[query.lower()])
            else:
                query = query.lower().replace('a', '$')\\
                                    .replace('e', '$')\\
                                    .replace('i', '$')\\
                                    .replace('o', '$')\\
                                    .replace('u', '$')
                
                ans.append(vowel[query])
        return ans

class Solution:
    def spellchecker(self, wordlist: List[str], queries: List[str]) -> List[str]:
        words = {w: w for w in wordlist}
        low ={w.lower(): w for w in wordlist[::-1]}
        vowel = {re.sub(\"[aeiou]\",'#',w.lower()): w for w in wordlist[::-1]}
        return [words.get(w) or low.get(w.lower()) or vowel.get(re.sub(\"[aeiou]\",'#',w.lower()),\"\") for w in queries]

class Solution:
    def spellchecker(self, wordlist: List[str], queries: List[str]) -> List[str]:
        self.wordset = set(wordlist)
        self.worddict_capitalized = {w.upper() : w for w in wordlist[::-1]}
        self.worddict_vowels = {self.replace_vowels(w.upper()) : w for w in wordlist[::-1]}
        
        #print(self.worddict_vowels)
        
        return [self.correct(q) for q in queries]
    
    def correct(self, q):
        if q in self.wordset:
            return q
        
        if q.upper() in self.worddict_capitalized:
            return self.worddict_capitalized[q.upper()]

        if self.replace_vowels(q.upper()) in self.worddict_vowels:
            return self.worddict_vowels[self.replace_vowels(q.upper())]
        
        return \"\"
    
    def replace_vowels(self, q):
        return q.replace(\"A\", \"!\").replace(\"E\", \"!\").replace(\"I\", \"!\").replace(\"O\", \"!\").replace(\"U\", \"!\")


class Solution:
    def spellchecker(self, wordlist: List[str], queries: List[str]) -> List[str]:
        set_case_sensitive = set()
        dict_case_insensitive = {}
        dict_case_vowel_insensitive = {}
                
        def replace_all(text):
            for c in \"aeiou\":
                text = text.replace(c, '*')
            return text
        
        for w in wordlist:
            set_case_sensitive.add(w)
            lw = w.lower()
            if lw not in dict_case_insensitive:
                dict_case_insensitive[lw] = w
            lwv = replace_all(lw)
            if lwv not in dict_case_vowel_insensitive:
                dict_case_vowel_insensitive[lwv] = w 
            
        res = []
        for q in queries:
            lq = q.lower()
            if q in set_case_sensitive:
                res.append(q)
            elif lq in dict_case_insensitive:
                res.append(dict_case_insensitive[lq])
            else:
                without_v = replace_all(lq)
                if without_v in dict_case_vowel_insensitive:
                    res.append(dict_case_vowel_insensitive[without_v])
                else:
                    res.append(\"\")
                    
        return res
                
        
                

#replacing the vowels ('a', 'e', 'i', 'o', 'u') of the query word with any vowel individually
#return the first such match in the wordlist.
#important! Capitalization has a higher priority than Vowel Errors

#backtrack + deque, O(n*4^l), O(4^l), TLE
#notice that in all candidates, return the matched one with minimum index
'''
from collections import defaultdict, deque
class Solution:
    def spellchecker(self, wordlist: List[str], queries: List[str]) -> List[str]:
        if not wordlist or not queries:
            return []
        
        hm = defaultdict(list)
        for i, word in enumerate(wordlist):
            hm[word].append(i)
          
        ans = []
        for query in queries:
            if query in hm:
                ans.append(query)
            else:
                idx = self.capitalization(query, hm)
                if idx != float('inf'):
                    ans.append(wordlist[idx])
                else:
                    candidates = self.vowel_replace(query)
                    j = 0
                    min_idx = float('inf')
                    while j < len(candidates):
                        idx = self.capitalization(candidates[j], hm)
                        min_idx = min(min_idx, idx)
                        j += 1
                    if min_idx != float('inf'):
                        ans.append(wordlist[min_idx])
                    else:
                        ans.append('')
        return ans
                    
                        
    def capitalization(self, query, hm):
        idx = float('inf')
        for key in hm:
            if query.lower() == key.lower():
                idx = min(idx, hm[key][0])
        return idx
    
    from collections import deque
    def vowel_replace(self, query):
        candidates = []
        dq = deque([query.lower()])
        visited = set([query])
        while dq:
            curr = dq.popleft()
            candidates.append(curr)
            for i, c in enumerate(curr):        #curr, not query
                if c in 'aeiouAEIOU':       #c may be lower or upper
                    for x in 'aeiou':
                        if abs(ord(c) - ord(x)) != 32:  #c != x:
                            candidate = curr[:i] + x + curr[i + 1:]
                            if candidate.lower() not in visited:
                                dq.append(candidate)
                                visited.add(candidate.lower())
        return candidates[1:]
'''     

#check Consonants, O(n^2 * l), O(n), TLE
'''
from collections import defaultdict
class Solution:
    def spellchecker(self, wordlist: List[str], queries: List[str]) -> List[str]:
        if not wordlist or not queries:
            return []
        
        hm = defaultdict(list)
        for i, word in enumerate(wordlist):
            hm[word].append(i)
          
        ans = []
        for query in queries:
            if query in hm:
                ans.append(query)
            else:
                idx = self.capitalization(query, hm)
                if idx != float('inf'):
                    ans.append(wordlist[idx])
                else:
                    idx = self.vowel_replace(query, hm)
                    if idx != float('inf'):
                        ans.append(wordlist[idx])
                    else:
                        ans.append('')
        return ans
                    
                        
    def capitalization(self, query, hm):
        idx = float('inf')
        for key in hm:
            if query.lower() == key.lower():
                idx = min(idx, hm[key][0])
        return idx
    
    def vowel_replace(self, query, hm):
        idx = float('inf')
        for key in hm:
            if self.is_matched(query, key):     #key, not query
                idx = min(idx, hm[key][0])
        return idx
    
    def is_matched(self, str1, str2):
        if len(str1) != len(str2):
            return False
        i, j = 0, 0
        while i < len(str1) and j < len(str2):
            if str1[i] not in 'aeiouAEIOU' and abs(ord(str1[i]) - ord(str2[j])) not in [0, 32]:     #辅音字母也可以有大小写
                return False
            if str1[i] in 'aeiouAEIOU' and str2[j] not in 'aeiouAEIOU':
                return False
            i += 1
            j += 1
        return True
'''

#3 hashmap/hashset
from collections import defaultdict
class Solution:
    def spellchecker(self, wordlist: List[str], queries: List[str]) -> List[str]:
        if not wordlist or not queries:
            return []
        
        word_exact = set(wordlist)
        word_capital = defaultdict(list)
        word_vowel = defaultdict(list)
        
        for word in wordlist:
            word_lower = word.lower()
            word_capital[word_lower].append(word)
            word_vowel[self.devowel(word_lower)].append(word)   #key is word_lower
          
        ans = []
        for query in queries:
            if query in word_exact:
                ans.append(query)
            else:
                query_lower = query.lower()
                if query_lower in word_capital:
                    ans.append(word_capital[query_lower][0])
                elif self.devowel(query_lower) in word_vowel:
                    ans.append(word_vowel[self.devowel(query_lower)][0])
                else:
                    ans.append('')
        return ans
    
    def devowel(self, word):
        ans = ''
        for i, c in enumerate(word):
            if c in 'aeiou':
                ans += '*'
            else:
                ans += c
        return ans
                    
                        

                
        
        
            
        
                


class Solution:
    def spellchecker(self, w: List[str], q: List[str]) -> List[str]:
        s = {i for i in w}
        d = {w[i].lower(): i for i in range(len(w)-1, -1, -1)}
        vowel = [\"a\", \"e\", \"i\", \"o\", \"u\"]
        # print(d, s)
        ans = []
        def func(i):
            n = len(i)
            # print(n, i)
            ls = [\"\"]
            ind = float(\"inf\")
            for j in range(n):
                if i[j] in vowel:
                    ls = [item+vow for item in ls for vow in vowel]
                else:
                    ls = [item+i[j] for item in ls]
            # print(i, ls)
            for item in ls:
                if item in d:
                    ind = min(ind, d[item])
                if ind == 0:
                    return ind
            return ind
        for i in q:
            if i in s:
                ans.append(i)
                continue
            i = i.lower()
            if i in d:
                ans.append(w[d[i]])
                continue
            flag = func(i)
            # print(flag)
            if flag == float(\"inf\"):
                ans.append(\"\")
            else:
                ans.append(w[flag])
        return ans

class Solution:
    def spellchecker(self, wordlist: List[str], queries: List[str]) -> List[str]:
        ww = set(wordlist)
        d = {}
        case = {}
        trs = str.maketrans('aeiou', '*****')
        for w in wordlist:
            r = w.lower()
            if r not in d:
                d[r] = w
            k = r.translate(trs)
            if k not in case:
                case[k] = w
        res = []
        for q in queries:
            if q in ww:
                res.append(q)
            else:
                x = q.lower()
                if x in d:
                    res.append(d[x])
                else:
                    y = x.translate(trs)
                    if y in case:
                        res.append(case[y])
                    else:
                        res.append('')
        return res

class Solution:
    def spellchecker(self, wordlist: List[str], queries: List[str]) -> List[str]:
        dic1, dic2, dic3 = {}, {}, {}
        for word in wordlist[::-1]:
            dic1[word] = word
            dic2[word.lower()] = word
            dic3[re.sub('[aeiou]', '*', word.lower())] = word
        return [dic1.get(q) or dic2.get(q.lower()) or dic3.get(re.sub('[aeiou]', '*', q.lower())) or \"\" for q in queries]
        # for q in queries:
        #     if q in dic1:
        #         ans.append(q)
        #         continue
        #     elif q.lower() in dic2:
        #         ans.append(dic2[q.lower()][0])
        #         continue
        #     elif re.sub('[aeiou]', '*', q.lower()) in dic3:
        #         ans.append(dic3[re.sub('[aeiou]', '*', q.lower())][0])
        #     else:
        #         ans.append(\"\")
        # # print(dic3)
        # return ans

def vowelprune(w):
    vowels={'a','e','i','o','u'}
    r=''
    for i in w:
        if i in vowels:r+='*'
        else:r+=i
    return r
def check(vow,se,fir,word):
    
    if word in se:return word
    word=word.lower()
    if word in fir:return fir[word]
    l=len(word)
    word=vowelprune(word)
    if word in vow:return vow[word]
    return \"\"
class Solution:
    def spellchecker(self, w: List[str], q: List[str]) -> List[str]:
        se=set(w)
        fir={}
        vow={}
        for i in w:
            z=i
            i=i.lower()
            if i not in fir:
                fir[i]=z
            j=vowelprune(i)
            if j not in vow:
                vow[j]=z
        res=[]
        for i in q:
            res.append(check(vow,se,fir,i))
        return res

class Solution:
    def spellchecker(self, wordlist: List[str], queries: List[str]) -> List[str]:
        all_words = set(wordlist)
        lowered = {}
        transformed = {}
        
        VOWELS = 'aeiou'
        
        def transform(word):
            return ''.join(['_' if char in VOWELS else char for char in word])
        
        for word in wordlist:
            lowered.setdefault(word.lower(), word)
            transformed.setdefault(transform(word.lower()), word)
        
        res = []
        for word in queries:
            if word in all_words:
                res.append(word)
                continue
            
            low = word.lower()
            if low in lowered:
                res.append(lowered[low])
                continue
            
            tran = transform(low)
            if tran in transformed:
                res.append(transformed[tran])
            else:
                res.append(\"\")
        
        return res

import re


class Solution:
    def spellchecker(self, wordlist: List[str], queries: List[str]) -> List[str]:
        def vowel_norm(inword):
            return re.sub(r\"[aeiou]\", \"a\", inword)

        lookup_lower, lookup_vowel = {}, {}
        for w in wordlist:
            l = w.lower()
            lookup_lower[l] = lookup_lower.get(l, []) + [w]
            lv = vowel_norm(l)
            lookup_vowel[lv] = lookup_vowel.get(lv, []) + [w]
        wordlist = set(wordlist)

        res = []
        for q in queries:
            qlow = q.lower()
            qvowel = vowel_norm(qlow)
            if q in wordlist:
                res.append(q)
            elif qlow in lookup_lower:
                res.append(lookup_lower[qlow][0])
            elif qvowel in lookup_vowel:
                res.append(lookup_vowel[qvowel][0])
            else:
                res.append(\"\")
        return res

class Solution:
    def spellchecker(self, wordlist: List[str], queries: List[str]) -> List[str]:
        vowels= {'a', 'e', 'i', 'o', 'u'}
        output =[]
        bucket = [[] for _ in range(8)]
        signaturebucket = [{} for _ in range(8)]
        
        def makesignature(word):
            result =0
            index =0
            for char in word:
                num = ord(char)
                if num < 97: #uppdercase -> lower:
                    num = num + 32
                if num == ord('a') or num == ord('i') or num == ord('e') or num == ord('o') or num == ord('u'):
                    num =97 #originally 'a'              
                num =num -97
                result = result + 21**index * num
                index +=1
            return result
        for word in wordlist:
            bucket[len(word)].append(word)
        for i in range(len(bucket)):
            for word in bucket[i]:
                signature = makesignature(word)
                dic = signaturebucket[i]

                if signature in dic:                    
                    dic[signature].append(word)
                else:
                    dic[signature] = [word]

        candidate = []
        for query in queries:
            if len(query) > 7:
                output.append(\"\")
                continue
            querysignature = makesignature(query)
            if len(signaturebucket[len(query)]) > 0:
                if querysignature in signaturebucket[len(query)]:
                    candidate = signaturebucket[len(query)][querysignature]
            
            if len(candidate) ==0:
                output.append(\"\")
                continue
      
            result=[3,\"\"]
            for i, word in enumerate(candidate):

                total=-1
                for i in range(len(query)):
                    if query[i] == word[i]:
                        cur = 0
                    elif query[i].lower() == word[i].lower():
                        cur = 1
                    elif query[i].lower() in vowels and word[i].lower() in vowels:
                        cur = 2
                    else:
                        total = 3
                        break
                    if total == -1:
                        total = cur
                    elif total < cur:
                        total = cur
                if total < result[0]:
                    result = [total, word]
            output.append(result[1])
            print (result[1])
        return output

vowels = {'a', 'e', 'i', 'o', 'u'}


class TrieNode:
    def __init__(self):
        self.ch = dict()
        self.words = []
        self.lower_words = defaultdict(list)

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        cur = self.root
        for l in word:
            lt = l.lower()
            if lt in vowels:
                lt = 'vowel'
            if lt not in cur.ch:
                cur.ch[lt] = TrieNode()
            cur = cur.ch[lt]
        cur.words.append(word)
        cur.lower_words[word.lower()].append(word)

    def search(self, word):
        cur = self.root
        for l in word:
            lt = l.lower()
            if lt in vowels:
                lt = 'vowel'
            if lt not in cur.ch:
                return ''
            cur = cur.ch[lt]
        if not cur.words:
            return ''
        lw = word.lower()
        if lw in cur.lower_words:
            if word in cur.lower_words[lw]:
                return word
            return cur.lower_words[lw][0]
        return cur.words[0]


class Solution:
    def spellchecker(self, wordlist: List[str], queries: List[str]) -> List[str]:
        trie = Trie()
        for word in wordlist:
            trie.insert(word)
        return [trie.search(word) for word in queries]

class Solution:
    def spellchecker(self, wordlist,queries):
        
        def getWords(wordlist):
            
            dict = {}
            
            for i in range(len(wordlist)):
                
                if wordlist[i] not in dict:
                    
                    dict[wordlist[i]] = i
                    
            return dict
        
        def GetVowels(wordlist):
            
            dict = {}
            
            for i in range(len(wordlist)):
                
                word = GetWord(wordlist[i])
                
                if word not in dict:
                    
                    dict[word] = wordlist[i]
                    
            return dict
            
        
        def GetCapital(wordlist):
            
            dict = {}
            
            for i in range(len(wordlist)):
                
                if wordlist[i].lower() not in dict:
                    
                    dict[wordlist[i].lower()] = wordlist[i]
                    
            return dict
        
        def helper(dict,word,ret):
        
            make = GetWord(word)
            
            return ret + [\"\"] if make not in dict else ret + [dict[make]]
        
        def GetWord(word):
            
            vowels = {\"a\":0,\"e\":0,\"i\":0,\"o\":0,\"u\":0}
            word = word.lower()
            
            s = \"\"
            
            for i in range(len(word)):
                
                if word[i] in vowels:
                    
                    s += \"1\"
                    
                else:
                    
                    s += word[i]
                    
            return s
                    
        
        ret = []
        
        words = getWords(wordlist)
        vowels = GetVowels(wordlist)
        capital = GetCapital(wordlist)
        
        for i in range(len(queries)):
            
            if queries[i] in words:
                
                ret.append(queries[i])
                
            elif queries[i].lower() in capital:
                
                ret.append(capital[queries[i].lower()])
            
            else:
                
                ret = helper(vowels,queries[i],ret)
            
        return ret
        

class Solution:
    def spellchecker(self, wordlist: List[str], queries: List[str]) -> List[str]:
        # 1. the same
        # 2. case diff, all in lowercase then compare, hash of wordlist(low:orig.list)
        # 3. vowel diff, same length, compare after removing? relative position info all aeiou with ' '? (compare all in lowercase)
        
        def rmvowel(word, iskeepcase=True):
            outword = ''
            word2 = word if iskeepcase else word.lower()
            for char in word2:
                if char in 'aeiou':
                    outword += ' '
                else:
                    outword += char
            return outword
        
        wordhash = defaultdict(list)
        for word in wordlist:
            wordhash[(word, 1)] = '' 
            wordhash[(word.lower(), 2)].append(word)
            wordhash[(rmvowel(word, False), 3)].append(word)
        
        outq = []
        for query in queries:
            if (query, 1) in wordhash:
                outq.append(query) # original format
            elif (query.lower(), 2) in wordhash:
                outq.append(wordhash[(query.lower(), 2)][0])
            elif (rmvowel(query, False), 3) in wordhash:
                outq.append(wordhash[(rmvowel(query, False), 3)][0])
            else:
                outq.append('')
        return outq


class Solution:
    def spellchecker(self, wordlist: List[str], queries: List[str]) -> List[str]:
        def devowel(word):
            return \"\".join('*' if c in 'aeiou' else c for c in word)

        words_perfect = set(wordlist)
        words_cap = {}
        words_vow = {}

        for word in wordlist:
            wordlow = word.lower()
            words_cap.setdefault(wordlow, word)
            words_vow.setdefault(devowel(wordlow), word)

        def solve(query):
            if query in words_perfect:
                return query

            queryL = query.lower()
            if queryL in words_cap:
                return words_cap[queryL]

            queryLV = devowel(queryL)
            if queryLV in words_vow:
                return words_vow[queryLV]
            return \"\"

        return map(solve, queries)

class Solution:
    def spellchecker(self, wordlist: List[str], queries: List[str]) -> List[str]:
        
        m_cap = {}
        for word in wordlist:
            new_ = []
            for c in word:
                new_.append(c.lower())
            new_ = ''.join(new_)
            if new_ not in m_cap:
                m_cap[new_] = word
        # print(m_cap)
        
        m_devow = {}
        for word in wordlist:
            new_ = []
            for c in word:
                c = c.lower()
                if c in set(['a','e','i','o','u']):
                    c = '*'
                new_.append(c.lower())
            new_ = ''.join(new_)
            if new_ not in m_devow:
                m_devow[new_] = word
        # print(m_devow)
        
        wordlist = set(wordlist)
        
        res = []
        for query in queries:
            if query in wordlist:
                res.append(query)
                continue
            
            lower_case = []
            for c in query:
                lower_case.append(c.lower())
            lower_case = ''.join(lower_case)
            if lower_case in m_cap:
                res.append(m_cap[lower_case])
                continue
            
            devowel = []
            for c in query:
                c = c.lower()
                if c in set(['a','e','i','o','u']):
                    c = '*'
                devowel.append(c)
            devowel = ''.join(devowel)
            if devowel in m_devow:
                res.append(m_devow[devowel])
                continue
            
            res.append(\"\")
        return res
        
                    

class Solution:
    def spellchecker(self, wordlist: List[str], queries: List[str]) -> List[str]:
        s = set(wordlist)
        d1 = {}
        d2 = {}
        for word in wordlist:
            if word.lower() not in d1:
                d1[word.lower()] = word
                
        for word in wordlist:
            word1 = word.lower()
            newWords = ['']
            for c in word1:
                newWords2 = []
                for newWord in newWords:
                    if c in 'aeiou':
                        for ch in 'aeiou':
                            newWords2.append(newWord + ch)
                    else:
                        newWords2.append(newWord + c)
                newWords = newWords2
            for newWord in newWords2:
                if newWord not in d2:
                    d2[newWord] = word
                        
        ans = []
        for q in queries:
            ql = q.lower()
            if q in s:
                ans.append(q)
            elif ql in d1:
                ans.append(d1[ql])
            elif ql in d2:
                ans.append(d2[ql])
            else:
                ans.append('')
        return ans

class Solution:
    def spellchecker(self, wordlist: List[str], queries: List[str]) -> List[str]:
        res = []
        # if totally same, then put that exact one
        # if case-insensitively same, then earlier one
        # check if indices for vowels are same, if same, then true
        
        vowels = [\"a\", \"e\", \"i\", \"o\", \"u\"]
        
        lookup = {}
        for word in wordlist:
            if not lookup.get(word.lower(), None):
                lookup[word.lower()] = word
                lookup[word] = word
                preprocessed_word = \"\".join([\"#\" if letter.lower() in vowels else letter.lower() for letter in word])
                if not lookup.get(preprocessed_word, None):
                    lookup[preprocessed_word] = word
            else:
                if not lookup.get(word, None):
                    lookup[word] = word
        
        
        for query in queries:
            # if totally same, then put that exact one
            # the_word = lookup.get(query, None)
            if query in lookup.keys() and query in wordlist:
                res.append(query)
                continue
                
            # if case-insensitively same, then earlier one
            the_word = lookup.get(query.lower(), None)
            if the_word:
                res.append(the_word)
                continue
            
            # check if indices for vowels are same, if same, then true
            preprocessed_query = \"\".join([\"#\" if letter.lower() in vowels else letter.lower() for letter in query])
            the_word = lookup.get(preprocessed_query, None)
            if the_word:
                res.append(the_word)
                continue
            
            res.append(\"\")
        
        return res
            

class Solution:
    def spellchecker(self, wordlist: List[str], queries: List[str]) -> List[str]:
        res = []
        # if totally same, then put that exact one
        # if case-insensitively same, then earlier one
        # check if indices for vowels are same, if same, then true
        
        vowels = [\"a\", \"e\", \"i\", \"o\", \"u\"]
        
        lookup = {}
        for word in wordlist:
            if not lookup.get(word.lower(), None):
                lookup[word.lower()] = word
                lookup[word] = word
                preprocessed_word = \"\".join([\"#\" if letter.lower() in vowels else letter.lower() for letter in word])
                if not lookup.get(preprocessed_word, None):
                    lookup[preprocessed_word] = word
            else:
                if not lookup.get(word, None):
                    lookup[word] = word
        
        for query in queries:
            # if totally same, then put that exact one
            # the_word = lookup.get(query, None)
            if query in lookup.keys() and query in wordlist:
                res.append(query)
                continue
                
            # if case-insensitively same, then earlier one
            the_word = lookup.get(query.lower(), None)
            if the_word:
                res.append(the_word)
                continue
            
            # check if indices for vowels are same, if same, then true
            preprocessed_query = \"\".join([\"#\" if letter.lower() in vowels else letter.lower() for letter in query])
            the_word = lookup.get(preprocessed_query, None)
            if the_word:
                res.append(the_word)
                continue
            
            res.append(\"\")
        
        print(lookup)
            
        return res
            

class Solution:
    def spellchecker(self, wordlist: List[str], queries: List[str]) -> List[str]:
        wordSet = set(wordlist)
        res = []
        words_dict = collections.defaultdict(list)
        vowels = {'a', 'e', 'i', 'o', 'u'}
        for i in range(len(wordlist)):
            word = wordlist[i]
            words_dict[word.lower()].append(i)
            wild_word = word.lower()
            for vowel in vowels:
                wild_word = wild_word.replace(vowel, '*')
            words_dict[wild_word.lower()].append(i)
        print(words_dict)
        for query in queries:
            wild_query = query.lower()
            for vowel in vowels:
                wild_query = wild_query.replace(vowel, '*')                    
            if query in wordSet:
                res.append(query)
            elif query.lower() in words_dict:
                res.append(wordlist[words_dict[query.lower()][0]])
            elif wild_query.lower() in words_dict:
                res.append(wordlist[words_dict[wild_query.lower()][0]])
            else:
                res.append(\"\")
        return res

class Solution:
    def spellchecker(self, wordlist: List[str], queries: List[str]) -> List[str]:
        res = []
        # if totally same, then put that exact one
        # if case-insensitively same, then earlier one
        # check if indices for vowels are same, if same, then true
        
        vowels = [\"a\", \"e\", \"i\", \"o\", \"u\"]
        
        lookup = {}
        for word in wordlist:
            if not lookup.get(word.lower(), None):
                lookup[word.lower()] = word
                lookup[word] = word
                preprocessed_word = \"\".join([\"#\" if letter.lower() in vowels else letter.lower() for letter in word])
                if not lookup.get(preprocessed_word, None):
                    lookup[preprocessed_word] = word
            else:
                if not lookup.get(word, None):
                    lookup[word] = word
        
        for query in queries:
            # if totally same, then put that exact one
            # the_word = lookup.get(query, None)
            if query in lookup.keys() and query in wordlist:
                res.append(query)
                continue
                
            # if case-insensitively same, then earlier one
            the_word = lookup.get(query.lower(), None)
            if the_word:
                res.append(the_word)
                continue
            
            # check if indices for vowels are same, if same, then true
            preprocessed_query = \"\".join([\"#\" if letter.lower() in vowels else letter.lower() for letter in query])
            print(preprocessed_query)
            the_word = lookup.get(preprocessed_query, None)
            if the_word:
                res.append(the_word)
                continue
            
            res.append(\"\")
        
        print(lookup)
            
        return res
            

from collections import defaultdict

class Solution:
    def spellchecker(self, wordlist: List[str], queries: List[str]) -> List[str]:
        VOWELS = {\"a\", \"e\", \"i\", \"o\", \"u\"}
        
        wordDict = {}
        for i in range(0, len(wordlist)):
            wordDict[wordlist[i]] = i
            
        wordIDict = defaultdict(list)
        for i in range(0, len(wordlist)):
            word = wordlist[i]
            wordIDict[word.lower()].append((i, word))
            
        ret = []
        
        
        def findByReplace(i, q):
            if i >= len(q): 
                return (len(wordlist), \"\")
            
            found = \"\"
            best = len(wordlist)
            if q[i] in VOWELS:
                for c in VOWELS:
                    q[i] = c
                    qword = ''.join(q)
                    if qword in wordIDict:
                        (n, word) = wordIDict[qword][0]
                        if n < best:
                            found = word
                            best = n
                    (n, word) = findByReplace(i+1, q)
                    if n < best:
                        found = word
                        best = n
            else:
                return findByReplace(i+1, q)
            
            return (best, found)

        
        
        for query in queries:
            if query in wordDict:
                ret.append(query)
            elif query.lower() in wordIDict:
                ret.append(wordIDict[query.lower()][0][1])
            else:  
                ret.append(findByReplace(0, list(query.lower()))[1])
            
        return ret

\"\"\"
Match exact, return exact
Match up to capitalizaion, return first
Match up to vowel error, return first
Return ''
\"\"\"

class Solution:
    def spellchecker(self, wordlist: List[str], queries: List[str]) -> List[str]:
        
        caps = {}
        vowels = {}
        setwordlist = set(wordlist)
        
        for i in wordlist:
            cap = i.lower()
            vowel = ''.join(['*' if x in 'aeiou' else x for x in i.lower()])
            if cap not in caps:
                caps[cap] = i
            if  vowel not in vowels:
                vowels[vowel] = i
            
        print(caps, vowels)
        
        ans = []
        
        for i in queries:
            cap = i.lower()
            vowel = ''.join(['*' if x in 'aeiou' else x for x in i.lower()])
            if i in setwordlist:
                ans.append(i)
            elif cap in caps:
                for x in caps:
                    if x == cap:
                        ans.append(caps[x])
                        break
            elif vowel in vowels:
                for x in vowels:
                    if x == vowel:
                        ans.append(vowels[x])
                        break
            else:
                ans.append('')
            
        return ans

class Solution:
    def spellchecker(self, wordlist: List[str], queries: List[str]) -> List[str]:
        
        vowels = set('aeiou')
        
        # Map lowercase words to word
        w = collections.defaultdict(list)
        for word in wordlist:
            w[word.lower()].append(word)
            
        # Map (vowel_count, len_word) to lowercase vowel-less words : word
        v = collections.defaultdict(list)
        vl = collections.defaultdict(list)
        for k in w:
            vowel_less = ''.join(char for char in k if char not in vowels)
            v[(len(vowel_less), len(k))].append(vowel_less)
            vl[vowel_less].append(k)
        
        res = []
        for q in queries:
            
            # 1. Case sensitive check
            k = q.lower()
            if k in w:
                res.append(q if (q in w[k]) else w[k][0])
                continue
                
            # 2. Vowel check
            vowel_less = ''.join(char for char in k if char not in vowels)
            if vowel_less in v[(len(vowel_less), len(k))]:
                for word in vl[vowel_less]:
                    if len(word) == len(k):
                        for a,b in zip(word,k):
                            if (a in vowels) != (b in vowels):
                                break
                        else:
                            res.append(w[word][0])
                            break
                else:
                    res.append(\"\")
            else:
                res.append(\"\")
        
        return res

class Solution:
    def spellchecker(self, wordlist: List[str], queries: List[str]) -> List[str]:
        
        caps = {}
        vowels = {}
        setwordlist = set(wordlist)
        
        for i in wordlist:
            cap = i.lower()
            vowel = ''.join(['*' if x in 'aeiou' else x for x in i.lower()])
            if cap not in caps:
                caps[cap] = i
            if  vowel not in vowels:
                vowels[vowel] = i
            
        print(caps, vowels)
        
        ans = []
        
        for i in queries:
            cap = i.lower()
            vowel = ''.join(['*' if x in 'aeiou' else x for x in i.lower()])
            if i in setwordlist:
                ans.append(i)
            elif cap in caps:
                for x in caps:
                    if x == cap:
                        ans.append(caps[x])
                        break
            elif vowel in vowels:
                for x in vowels:
                    if x == vowel:
                        ans.append(vowels[x])
                        break
            else:
                ans.append('')
            
        return ans

class TrieNode:
    def __init__(self):
        self.isWord = False
        self.children = {}
        self.wordMatches = []
class SpellCheckTrie:

    def __init__(self):
        self.root = TrieNode()
        self.exactRoot = TrieNode()
        self.vowelRoot = TrieNode()


    def addWord(self, word):

        it = self.root
        exactIt = self.exactRoot
        vowelIt = self.vowelRoot

        for c in word:
            loweredChar = ord(c) | 32


            vowNormalizedChar = loweredChar
            if c in ['a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U']:
                vowNormalizedChar = -1 # We use a unique index to reference all vowels
            childNode = it.children.get(loweredChar)
            exactChildNode = exactIt.children.get(ord(c))
            vowelChildNode = vowelIt.children.get(vowNormalizedChar)

            if not childNode:
                childNode = TrieNode()
                it.children[loweredChar] = childNode
            if not exactChildNode:
                exactChildNode = TrieNode()
                exactIt.children[ord(c)] = exactChildNode

            if not vowelChildNode:
                vowelChildNode = TrieNode()
                vowelIt.children[vowNormalizedChar] = vowelChildNode    

            it = childNode
            exactIt = exactChildNode
            vowelIt = vowelChildNode

        it.isWord = True
        it.wordMatches.append(word)
        exactIt.isWord = True
        vowelIt.isWord = True
        vowelIt.wordMatches.append(word)

    def searchWord(self, word):
        it = self.root
        exactIt = self.exactRoot
        vowelIt = self.vowelRoot

        for c in word:
            loweredChar = ord(c) | 32
            vowNormalizedChar = loweredChar
            if c in ['a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U']:
                vowNormalizedChar = -1
        
            
            if it:
                childNode = it.children.get(loweredChar)
            if exactIt:
                exactChildNode = exactIt.children.get(ord(c))
            if vowelIt:
                vowelChildNode = vowelIt.children.get(vowNormalizedChar)

            if childNode:
                it = childNode
            else:
                it = None
            if exactChildNode:
                exactIt = exactChildNode
            else:
                exactIt = None
                
            if vowelChildNode:
                vowelIt = vowelChildNode
            else:
                vowelIt = None

        if exactIt and exactIt.isWord:
            return word

        if it and it.isWord:
            return it.wordMatches[0]

        if vowelIt and vowelIt.isWord:
            return vowelIt.wordMatches[0]

        return \"\"
    

class Solution:
    def spellchecker(self, wordlist: List[str], queries: List[str]) -> List[str]:
        trie = SpellCheckTrie()
        for word in wordlist:
            trie.addWord(word)
            
        return [trie.searchWord(q) for q in queries]
            
        

class Solution:
    def spellchecker(self, wordlist: List[str], queries: List[str]) -> List[str]:
        words_ori = {}
        words_cap = {}
        words_vowel = {}
        
        vowel = ['a', 'e', 'i', 'o', 'u']
        
        def gen_vowel(cur, val, pos):
            if pos >= len(cur):
                return
            if cur[pos] in vowel:
                for i in vowel:
                    if i != cur[pos]:
                        key = (cur[0:pos] + i + cur[pos+1:]).lower()
                        try:
                            if words_vowel[key]:
                                continue
                        except:
                            words_vowel[key] = val
                        gen_vowel(key, val, pos+1)
            gen_vowel(cur, val, pos+1)
        
        for i in wordlist:
            words_ori[i] = i
            temp = i[:]
            gen_vowel(temp, i, 0)
            try:
                if words_cap[temp.lower()]:
                    continue
            except:
                temp = temp.lower()
                words_cap[temp] = i
                
        # print(words_ori, words_cap, words_vowel)
        
        ans = []
        for i in queries:
            try:
                if words_ori[i]:
                    ans.append(i)
                    continue
            except: pass
            
            try:
                if words_cap[i.lower()]:
                    ans.append(words_cap[i.lower()])
                    continue
            except: pass
            
            try:
                if words_vowel[i.lower()]:
                    ans.append(words_vowel[i.lower()])
                    continue
            except: pass
            
            ans.append(\"\")

        return ans
                

class Node:
    def __init__(self):
        self.kids = defaultdict(Node)
        self.words = []
class Trie:
    def __init__(self):
        self.head = Node()
        self.cache = defaultdict(str)
        self.exacts = defaultdict(str)
        self.novowels = defaultdict(str)
        self.time = 0
        self.sortkey = {}
        
    def add(self, word):
        curr = self.head
        if word.lower() not in self.cache:
            self.cache[word.lower()] = word
        self.exacts[word] = word
        
        def novo(word):
            grp = list(word)
            for i,g in enumerate(grp):
                if g.lower() in 'aeiou':
                    grp[i] = '*'
                else:
                    grp[i] = grp[i].lower()
            return ''.join(grp)
        
        nvwl = novo(word)
        if nvwl not in self.novowels:
            print(nvwl, word)
            self.novowels[nvwl] = word
        
        self.time += 1
        self.sortkey[word] = self.time
        temp = word.lower()
        for w in temp:
            curr = curr.kids[w]
        
        curr.words.append(word)
        
    def search(self, word, start=None):
        def novo(word):
            grp = list(word)
            for i,g in enumerate(grp):
                if g.lower() in 'aeiou':
                    grp[i] = '*'
                else:
                    grp[i] = grp[i].lower()
                    
            return ''.join(grp)
                    
        if word in self.exacts and start is None:
            return word
        if word.lower() in self.cache and start is None:
            return self.cache[word.lower()]
        if novo(word) in self.novowels and start is None:
            print(word, novo(word), self.novowels[novo(word)])
            return self.novowels[novo(word)]
        # print(self.novowels)
        
        if start is None:
            start = self.head
        if word == \"vavkmj\":
            print(\"search.word\", word, [k for k in start.kids['v'].kids.keys()])     
        curr = start

        
        for i,w in enumerate(word):
            if w.lower() in 'aeiou':
                res = []
                for c in curr.kids.keys():
                    if c in 'aeiou':
                        out = self.search(word[i+1:], curr.kids[c])
                        if out != \"\":
                            res.append(out)
                if res:
                    print(\"resss\", word, res)
                    res.sort(key=lambda x:self.sortkey[x])
                    
                    print(\"resss2\", word, res)
                    return res[0]
                return \"\"
            elif w in curr.kids:
                curr = curr.kids[w]
            elif w.lower() in curr.kids:
                curr = curr.kids[w.lower()]
            elif w.upper() in curr.kids:
                curr = curr.kids[w.upper()]
            else:
                break
                # assert(False)
                # if w.lower() in 'aeiou':
                #     if word == \"vavkmj\":
                #         print(curr.kids.keys())
                #     for c in curr.kids.keys():
                #         if c in 'aeiou':
                #             out = self.search(c+word[i+1:], curr)
                #             if out != \"\":
                #                 return out
                #     return \"\"
                # else:
                #     return \"\"
        # print(\"curr.words\",word, \"->\", curr.words)     
        if curr and curr.words:
            curr.words.sort(key=lambda x:self.sortkey[x])
            return curr.words[0]
        return \"\"
    

class Solution:
    def spellchecker(self, wordlist: List[str], queries: List[str]) -> List[str]:
        tree = Trie()
        
        for word in wordlist:
            tree.add(word)
            
        out = []
        for q in queries:
            res = tree.search(q)
            # print(q,\"->\", res)
            if res == \"\" and q and q[0].lower() in 'aeiou':
                for v in 'aeiou':
                    if q[0] != v:
                        res = tree.search(v+q[1:])
                        if res != \"\":
                            break
            # if q == \"aai\":
            #     print(q,\"->\", res)
            out.append(res)
        
        # print(out)
        return out

class Solution:
    def spellchecker(self, wordlist: List[str], queries: List[str]) -> List[str]:
        wordset = set(wordlist)
        wordset_lower = set()
        code_map = dict()
        for word in wordlist:
            wordset_lower.add(word.lower())
            code = encode(word)
            if code not in code_map:
                code_map[code] = word
        answer = []
        
        for query in queries:
            if query in wordset:
                answer.append(query)
            elif query.lower() in wordset_lower:
                for word in wordlist:
                    if word.lower() == query.lower():
                        answer.append(word)
                        break
            elif encode(query) in code_map:
                answer.append(code_map[encode(query)])
            else:
                answer.append('')
                
        return answer
                
                
def encode(word):
    code = []
    for c in word.lower():
        if c in {'a', 'e', 'i', 'o', 'u'}:
            code.append('@')
        else:
            code.append(c)
    return ''.join(code)

class Solution:
    def spellchecker(self, wordlist: List[str], queries: List[str]) -> List[str]:
        capital = defaultdict(list)
        for word in wordlist:
            capital[word.lower()].append(word)
            
        vowels = defaultdict(list)
        for word in wordlist:
            newword = word
            for ch in \"aeiouAEIOU\":
                newword = newword.replace(ch, \"$\")
            vowels[newword.lower()].append(word)
        ans = []        
        for q in queries:
            if q in wordlist:
                ans.append(q)
            elif q.lower() in capital:
                ans.append(capital[q.lower()][0])
            else:
                newq = q
                for ch in \"aeiouAEIOU\":
                    newq = newq.replace(ch, \"$\")
                if newq.lower() in vowels:
                    ans.append(vowels[newq.lower()][0])
                else:
                    ans.append(\"\")
            
        return ans

vowels = set([\"a\", \"e\", \"o\", \"i\", \"u\"])

class Solution:
    def spellchecker(self, wordlist: List[str], queries: List[str]) -> List[str]:
        first_match = defaultdict(str)
        vowel_match = defaultdict(str)
        word_list = set(wordlist)
        for word in wordlist:
            lower_word = word.lower()
            if not first_match.get(lower_word):
                first_match[lower_word] = word
            letters = list(lower_word)
            self.find_valid_word(letters, 0, word, vowel_match)
                    
            
        results = []
        for word in queries:
            if word in word_list:
                results.append(word)
            else:
                lower_word = word.lower()
                if lower_word in first_match:
                    results.append(first_match[lower_word])
                elif lower_word in vowel_match:
                    results.append(vowel_match[lower_word])
                else:
                    results.append(\"\")
        return results
    
    def find_valid_word(self, letters, start, curr_word, first_match):
        new_str = \"\".join(letters)
        if new_str not in first_match:
            first_match[new_str] = curr_word
        for i in range(start, len(letters)):
            if self.is_vowel(letters[i]):
                for vowel in vowels:
                    letters[i] = vowel
                    valid_word = self.find_valid_word(letters, i + 1, curr_word, first_match)
        return \"\"
          
    def is_vowel(self, char):
        return char in vowels

def lower(y):return y.lower()
class Solution:
    
    def checkvowel(self,word,dic,vowels,Results):
        vowelWord = ''
        for y in word:
            if y in vowels:vowelWord+='_'
            else :vowelWord+=lower(y)
        if vowelWord in dic:
            Results += [dic[vowelWord]]
            return True
        else :return False
            
    def spellchecker(self, wordlist: List[str], queries: List[str]) -> List[str]:
        vowels = ['a', 'e', 'i', 'o', 'u']
        dic_vowels = {}
        for x in wordlist: 
            vowelWord = ''
            for y in x:
                if lower(y) in vowels:vowelWord+='_'
                else :vowelWord+=lower(y)
            if vowelWord not in dic_vowels:
                dic_vowels[vowelWord] = x
        
        wordlist_ = {}
        for x in wordlist:
            if lower(x) not in wordlist_:
                wordlist_[lower(x)]=x
        
        Results = []
        for word in queries:
            if word in wordlist:
                Results += [word]
            elif lower(word) in wordlist_:
                Results += [wordlist_[lower(word)]]
            elif self.checkvowel(lower(word),dic_vowels,vowels,Results):
                pass
            else :Results+=[\"\"]
        return Results
    
            

class Solution:
    def spellchecker(self, wordlist: List[str], queries: List[str]) -> List[str]:
        def generate(string):
            if not string:
                yield string
            else:
                if string[0] in vowel:
                    for v in vowel:
                        for g in generate(string[1:]):
                            yield v + g
                else:
                    for g in generate(string[1:]):
                        yield string[0] + g
        
        dicti, vowel, ans = {}, {\"a\", \"e\", \"i\", \"o\", \"u\"}, []
        for word in wordlist:
            cur = word.lower()
            if cur not in dicti:
                dicti[cur] = [set(), None, None]
            dicti[cur][0].add(word)
            if dicti[cur][1] is None:
                dicti[cur][1] = word
            for new in generate(cur):
                if new not in dicti:
                    dicti[new] = [set(), None, None]
                if dicti[new][2] is None:
                    dicti[new][2] = word
        for query in queries:
            cur, flag = query.lower(), 1
            if cur in dicti:
                if query in dicti[cur][0]:
                    ans.append(query)
                    flag = 0
                elif dicti[cur][1] is not None:
                    ans.append(dicti[cur][1])
                    flag = 0
            if flag:
                for new in generate(cur):
                    if new in dicti and dicti[new][2] is not None:
                        ans.append(dicti[new][2])
                        flag = 0
                        break
            if flag:
                ans.append(\"\")
        return ans

class Solution:
    def spellchecker(self, wordlist: List[str], queries: List[str]) -> List[str]:
        first = set(wordlist)
        second = [word.lower() for word in wordlist]
        third = []
        for word in wordlist:
            tmp = \"\"
            for c in word:
                if c not in {'a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U'}:
                    tmp += c
                else:
                    tmp += 'a'
            third.append(tmp.lower())
        res = []
        for query in queries:
            if query in first:
                res.append(query)
                continue
            try:
                idx = second.index(query.lower())
                res.append(wordlist[idx])
                continue
            except ValueError:
                pass
            vowelIns = \"\"
            for c in query:
                if c not in {'a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U'}:
                    vowelIns += c
                else:
                    vowelIns += 'a'
            try:
                idx = third.index(vowelIns.lower())
                res.append(wordlist[idx])
            except ValueError:
                res.append(\"\")
        return res

class Solution:
    def spellchecker(self, wordlist: List[str], queries: List[str]) -> List[str]:
        capLookup = {}
        vowelLookup = {}
        res = []
        
        for word in wordlist:
            if word.lower() not in capLookup:
                capLookup[word.lower()] = word
            starword = ''.join('*' if l in 'aeiou' else l for l in word.lower())
            if starword not in vowelLookup:
                vowelLookup[starword] = word
        
        for query in queries:
            if query in wordlist:
                res.append(query)
                continue
            if query.lower() in capLookup:
                res.append(capLookup[query.lower()])
                continue
            starquery = ''.join('*' if l in 'aeiou' else l for l in query.lower())
            if starquery in vowelLookup:
                res.append(vowelLookup[starquery])
                continue
            else:
                res.append('')
        return res


class Solution:
    def spellchecker(self, wordlist: List[str], queries: List[str]) -> List[str]:
        vowels = collections.defaultdict(list)
        capitalization = collections.defaultdict(list)
        
        ans = []
        for word in wordlist:
            w = word.lower()
            for vowel in 'aeiouAEIOU':
                w = w.replace(vowel,\"*\")
            vowels[w].append(word)
        
        for word in wordlist:
            capitalization[word.lower()].append(word)
        wordlist_set = set(wordlist)
        for word in queries:
            if word in wordlist:
                ans.append(word)
                continue
            word_lower = word.lower()
            if word_lower in capitalization:
                ans.append(capitalization[word_lower][0])
                continue
                
            for vowel in 'aeiouAEIOU':
                word_lower = word_lower.replace(vowel,\"*\")
            if word_lower in vowels:
                ans.append( vowels[word_lower][0])
                continue
            else:
                ans.append(\"\")
                
        return ans  
            

class Solution:
    def maskVowels(self, word) -> str:
        VOWELS = ['a', 'e', 'i', 'o', 'u']
        masked_word = word.lower()
        for vowel in VOWELS:
            masked_word = masked_word.replace(vowel, '_')
        return masked_word
    
    def spellchecker(self, wordlist: List[str], queries: List[str]) -> List[str]:
        map = {}
        output = []
                       
        for word in reversed(wordlist):
            # if word.lower() not in map:
            map[word.lower()] = word
            masked_word = self.maskVowels(word)
            map[masked_word] = word
        
        
        for word in queries:
            word_lower = word.lower()
            word_masked = self.maskVowels(word)
            if word in wordlist:
                output.append(word)
            elif word in map:
                output.append(map[word])
            elif word_lower in map:
                output.append(map[word_lower])
            elif word_masked in map:
                output.append(map[word_masked])
            else:
                output.append(\"\")
        
        return output
   

class Solution:
    def spellchecker(self, wordlist: List[str], queries: List[str]) -> List[str]:
        def replace(w):
            return re.sub(r'[aeiou]', '*', w)
        
        lowercases = {}
        for w in wordlist:
            ww = w.lower()
            if ww not in lowercases:
                lowercases[ww] = w
            ww = replace(ww)
            if ww not in lowercases:
                lowercases[ww] = w
        words = set(wordlist)
        answer = []
        for w in queries:
            if w in words:
                answer.append(w)
                continue
            ww = w.lower()
            answer.append(lowercases.get(ww, lowercases.get(replace(ww), '')))
        return answer

class Solution:
    def spellchecker(self, wordlist: List[str], queries: List[str]) -> List[str]:
        def helper(query):
            # check for exact
            if query in wordlist:
                return query
            # check for first case-insensitive match
            if query.lower() in lowercase:
                return wordlist[lowercase[query.lower()]]
                
            # check for vowel error match
            withoutVowelQuery = \"\"
            for char in query:
                if char.lower() in vowels:
                    withoutVowelQuery += '#'
                else:
                    withoutVowelQuery += char.lower()
                    
            if withoutVowelQuery in without_vowel:
                return wordlist[without_vowel[withoutVowelQuery]]
            # else return empty string
            return \"\"
        
        res = []
        
        lowercase = {}
        
        for i, word in enumerate(wordlist):
            if word.lower() not in lowercase:
                lowercase[word.lower()] = i
        
        vowels = {'a', 'e', 'i', 'o', 'u'}
        without_vowel = {}
        
        for i, word in enumerate(wordlist):
            newWord = \"\"
            for char in word:
                if char.lower() in vowels:
                    newWord += '#'
                else:
                    newWord += char.lower()
            if newWord not in without_vowel:
                without_vowel[newWord] = i
        
        # print(wordlist)
        # print(lowercase)
        # print(without_vowel)
        
        for query in queries:
            res.append(helper(query))
        return res

class Solution:
    def maskVowels(self, word) -> str:
        return \"\".join('*' if c in 'aeiou' else c
                           for c in word)
        # VOWELS = ['a', 'e', 'i', 'o', 'u']
        # masked_word = word
        # for vowel in VOWELS:
        #     masked_word = masked_word.replace(vowel, '_')
        # return masked_word
    
    def spellchecker(self, wordlist: List[str], queries: List[str]) -> List[str]:
        map = {}
        output = []
                       
        for word in reversed(wordlist):
            lower = word.lower()
            map[lower] = word
            masked_word = self.maskVowels(lower)
            map[masked_word] = word
        
        
        for word in queries:
            word_lower = word.lower()
            word_masked = self.maskVowels(word_lower)
            if word in wordlist:
                output.append(word)
            elif word in map:
                output.append(map[word])
            elif word_lower in map:
                output.append(map[word_lower])
            elif word_masked in map:
                output.append(map[word_masked])
            else:
                output.append(\"\")
        
        return output
   

class Solution:
    def spellchecker(self, wordlist: List[str], queries: List[str]) -> List[str]:
        # for i in range(len(wordlist)):
        #     if wordlist[i] != queries[i]:
        #         print(i,wordlist[i], queries[i])
        #         break
        
        lw = {}
        for i in wordlist:
            if i.lower() not in lw:
                lw[i.lower()] = i
        vfw = {}
        for j in wordlist:
            if re.sub('[aeiou]','*', j.lower()) not in vfw:
                vfw[re.sub('[aeiou]','*', j.lower())] = j
        l = len(queries)
        res = []
        for i in range(l):
            low = queries[i].lower()
            wild = ''.join(['*' if i in 'aeiou' else i for i in low])
            if queries[i] in wordlist:
                res.append(queries[i])
                continue
            elif low in lw:
                res.append(lw[low])
            elif wild in vfw:
                res.append(vfw[wild])
            else:
                res.append('')
        return res
        
#         low_origin, wild_origin = collections.defaultdict(str), collections.defaultdict(str)
#         s = set(wordlist)            
#         def to_wild(word): return ''.join(['*' if c in 'aeiou' else c for c in word])
        
#         for word in wordlist:
#             low = word.lower()
#             if low not in low_origin: low_origin[low] = word
#             wild = to_wild(low)
#             if wild not in wild_origin: wild_origin[wild] = word
#         print()
#         ans = []
#         for query in queries:
#             low = query.lower()
#             wild = to_wild(low)
#             if query in s: ans.append(query)
#             elif low in low_origin: ans.append(low_origin[low])    
#             elif wild in wild_origin: ans.append(wild_origin[wild]) 
#             else: ans.append('')
#         return ans



class Solution:
    def maskVowels(self, word) -> str:
        VOWELS = ['a', 'e', 'i', 'o', 'u']
        masked_word = word
        for vowel in VOWELS:
            masked_word = masked_word.replace(vowel, '_')
        return masked_word
    
    def spellchecker(self, wordlist: List[str], queries: List[str]) -> List[str]:
        map = {}
        output = []
                       
        for word in reversed(wordlist):
            lower = word.lower()
            map[lower] = word
            masked_word = self.maskVowels(lower)
            map[masked_word] = word
        
        
        for word in queries:
            word_lower = word.lower()
            word_masked = self.maskVowels(word_lower)
            if word in wordlist:
                output.append(word)
            elif word in map:
                output.append(map[word])
            elif word_lower in map:
                output.append(map[word_lower])
            elif word_masked in map:
                output.append(map[word_masked])
            else:
                output.append(\"\")
        
        return output
   

class Solution:
    def spellchecker(self, wordlist: List[str], queries: List[str]) -> List[str]:
        if not wordlist or not queries:
            return None
        
        wordlistSet = set(wordlist)
        wordUpper ={}
        wordVowels = {}
        res = []
        
        
        def getwordWithVowelErrors(s):
            newWord =\"\"
            vowels = {'a','e','i','o','u'}
            for ch in s:
                if ch in vowels:
                    newWord += \"*\"
                else:
                    newWord += ch
            return newWord
                    
        
        
        for  w in wordlist:
            lower = w.lower()
            if lower not in wordUpper:
                wordUpper[lower] = w
                
            wordWithVowelErrors = getwordWithVowelErrors(lower)
            if wordWithVowelErrors not in wordVowels:
                wordVowels[wordWithVowelErrors] = w
                
        for q in queries:
            if q:
                lower = q.lower()
                wordWithVowelErrors = getwordWithVowelErrors(lower)
                if q in wordlistSet:
                    res.append(q)
                elif lower in wordUpper:
                    res.append(wordUpper[lower])
                elif wordWithVowelErrors in wordVowels:
                    res.append(wordVowels[wordWithVowelErrors])
                else:
                    res.append(\"\")
                    
        return res
        

class Solution:
    def replaceVowels(self, s):
        return \"\".join(['*' if x in ['a','e','i','o','u'] else x for x in s.lower()])
    
    def spellchecker(self, wordlist: List[str], queries: List[str]) -> List[str]:
        result = [\"\" for q in queries]
        
        capitalizationDict = {}
        vowelDict = {}
        
        for w in wordlist:
            w_lower = w.lower()
            if w_lower not in capitalizationDict:
                capitalizationDict[w_lower] = []
            capitalizationDict[w_lower].append(w)
            
            w_vowel = self.replaceVowels(w)
            if w_vowel not in vowelDict:
                vowelDict[w_vowel] = []
                
            vowelDict[w_vowel].append(w)
            
        wordSet = set(wordlist)
        
        for i in range(len(queries)):
            if queries[i] in wordSet:
                result[i] = queries[i]
            elif queries[i].lower() in capitalizationDict:
                result[i] = capitalizationDict[queries[i].lower()][0]
            elif self.replaceVowels(queries[i]) in vowelDict:
                result[i] = vowelDict[self.replaceVowels(queries[i])][0]
                
        return result