Sponsored
Sponsored
This approach uses three types of hash maps:
Time Complexity: O(N + M) per query, where N is the length of the wordlist and M is the length of the longest query.
Space Complexity: O(N), to store the dictionaries for the wordlist.
1def spellChecker(wordlist, queries):
2 def normalize_word(word):
3 return ''.join(['*' if c in 'aeiouAEIOU' else c for c in word])
4 exact_matches = set(wordlist)
5 case_matches = {w.lower(): w for w in reversed(wordlist)}
6 vowel_matches = {}
7 for w in reversed(wordlist):
8 vw = normalize_word(w.lower())
9 if vw not in vowel_matches:
10 vowel_matches[vw] = w
11 def find_match(query):
12 if query in exact_matches:
13 return query
14 low_query = query.lower()
15 if low_query in case_matches:
16 return case_matches[low_query]
17 vow_query = normalize_word(low_query)
18 if vow_query in vowel_matches:
19 return vowel_matches[vow_query]
20 return ""
21 return [find_match(query) for query in queries]This solution initializes three dictionaries for exact, case-insensitive, and vowel-insensitive matches. The normalize_word function transforms words by replacing all vowels with '*'. For each query, the solution checks the query against these dictionaries and returns results based on the first successful match.
This approach utilizes a trie data structure to accommodate the various search conditions:
Time Complexity: O(N + M) per query, where N is the length of the wordlist and M is the length of the longest query.
Space Complexity: O(N), for storing each transformed mapping in the maps used.
1function spellchecker(wordlist,
This JavaScript implementation captures the essence of the trie strategy using objects. It leverages function maskVowels to replace vowels with asterisks for vowel-insensitive matching. The solution goes through a sequential check for matches and returns the correct form based on the first match success.