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.

Source: leetcode | Difficulty: MEDIUM
Tags: String algorithms

Data structures

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

Solutions:
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 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]:
		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
		res = []
		for q in queries:
			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:]
					if imd_w in cache:
						res.append(cache[imd_w])
					else:
						res.append('')
		return res


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)
		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, 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


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: List[str], queries: List[str]) -> List[str]:

		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)
			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]:
		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]:
		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]:
		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]:
		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]:

		def replace(w):
			return re.sub('[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]:
		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