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:
wordlist = ["yellow"], query = "YellOw": correct = "yellow"wordlist = ["Yellow"], query = "yellow": correct = "Yellow"wordlist = ["yellow"], query = "yellow": correct = "yellow"('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.
wordlist = ["YellOw"], query = "yollow": correct = "YellOw"wordlist = ["YellOw"], query = "yeellow": correct = "" (no match)wordlist = ["YellOw"], query = "yllw": correct = "" (no match)In addition, the spell checker operates under the following precedence rules:
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"]
Example 2:
Input: wordlist = ["yellow"], queries = ["YellOw"] Output: ["yellow"]
Constraints:
1 <= wordlist.length, queries.length <= 50001 <= wordlist[i].length, queries[i].length <= 7wordlist[i] and queries[i] consist only of only English letters.This approach uses three types of hash maps:
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.
Java
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.
This approach utilizes a trie data structure to accommodate the various search conditions:
This C++ solution builds maps for case-insensitive and vowel-insensitive matches from the wordlist. During querying, each query is transformed and searched against these data structures in the order of priority. It offers a clean way to handle multiple match types while efficiently searching.
JavaScript
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.
| Approach | Complexity |
|---|---|
| Hash Maps for Different Match Types | Time Complexity: O(N + M) per query, where N is the length of the wordlist and M is the length of the longest query. |
| Trie with Search Functions for Different Match Types | Time Complexity: O(N + M) per query, where N is the length of the wordlist and M is the length of the longest query. |
Junior Software Dev vs Senior Dev solving Valid Anagram • Greg Hogg • 693,669 views views
Watch 9 more video solutions →Practice Vowel Spellchecker with our built-in code editor and test cases.
Practice on FleetCode