Vowel Spellchecker Solution In C++/Java/Python/JS
Problem Description
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
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"]
Explanation:
Query = "kite"Exact match with "kite" in wordlist. Return "kite".
Query = "Kite"Matches "kite" (case-insensitive). Return the first match from wordlist, which is "KiTe".
Query = "KiTe"Exact match with "KiTe" in wordlist. Return "KiTe".
Query = "Hare"Exact match with "Hare" in wordlist. Return "Hare".
Query = "HARE"Matches "Hare" (case-insensitive). Return the first match from wordlist, which is "hare".
Query = "Hear"No exact or case-insensitive match. Also, no match after replacing vowels. Return "".
Query = "hear"Same as "Hear". Return "".
Query = "keti"Matches "KiTe" after replacing vowels ('e' with 'i'). Return "KiTe".
Query = "keet"No exact or vowel-matching word found. Return "".
Query = "keto"Matches "KiTe" after replacing vowels ('e' with 'o'). Return "KiTe".
Input:
wordlist = ["yellow"]
queries = ["YellOw"]
Output: ["yellow"]
Explanation:
Query = "YellOw"
Matches "yellow" (case-insensitive). Return "yellow".
Constraints
1 <= wordlist.length, queries.length <= 5000
1 <= wordlist[i].length, queries[i].length <= 7
wordlist[i] and queries[i] consist only of only English letters.
The problem requires us to implement a spellchecker that modifies the queries to match the correct word from the given wordlist. Let’s, for now, set aside the modification aspect and focus on the primary objective: accurately identifying and returning the correct word from the wordlist for each query based on the specified rules of capitalization and vowel errors.
Optimal Approach
Intuition
Imagine you’re given a wordlist and a set of queries, and your task is to match each query to the most suitable word from the wordlist based on a set of rules. Your main goal is to identify the correct word (or return an empty string if no match exists) for every query, focusing primarily on the matching process itself.
What Does Matching Mean?
For each query, the goal is to find the closest match from the wordlist based on these rules:
Exact Match, If the query matches a word exactly (case-sensitive), return the word.
Capitalization Match, If the query matches a word case-insensitively, return the first such match from the wordlist. Vowel Errors Match, If the query matches a word after replacing its vowels ('a', 'e', 'i', 'o', 'u') with any vowel (case-insensitive), return the first such match.
Understanding the Matching Process
Exact Match:
If the query exactly matches a word in the wordlist (case-sensitive), return it immediately. For example: Wordlist = ["Yellow"], Query = "Yellow" → Match found → Return "Yellow".
Capitalization Match:
Convert both the query and the wordlist words to lowercase and check for matches.
If a match is found, return the first word from the wordlist with the correct case.
For example: Wordlist = ["Yellow"], Query = "yellow" → Match found → Return "Yellow".
Vowel Errors Match:
For each word in the wordlist, replace all vowels with a placeholder (e.g., '*') to form a vowel-neutral representation. Do the same for the query and check for matches.
If a match is found, return the first word from the wordlist with the correct case.
For example: Wordlist = ["Yellow"], Query = "yollow" → Match found after replacing vowels → Return "Yellow".
What Do We Need to Track?
Exact Matches: This is straightforward; check directly in the wordlist.
Case-Insensitive Matches: Use a dictionary that maps lowercase words to their original case in the wordlist.
Vowel Errors Matches: Use a second dictionary where both the wordlist words and queries are transformed into their vowel-neutral forms, allowing for efficient lookups.
Approach
Given:
wordlist = ["KiTe", "kite", "hare", "Hare"]
queries = ["kite", "Kite", "KiTe", "Hare", "HARE", "Hear", "hear", "keti", "keet", "keto"]
Iteration 1:
Adding exact matches to exactMatches
Add each word in wordlist to the exactMatches set. exactMatches = {"KiTe", "kite", "hare", "Hare"}
Iteration 2:
Adding case-insensitive matches to caseInsensitiveMap
Convert each word to lowercase and add it to caseInsensitiveMap (only the first occurrence of each lowercase word is stored). caseInsensitiveMap = { "kite" → "kite", "hare" → "hare" }
Iteration 3:
Adding vowel-normalized matches to vowelMap
Action: Normalize vowels in each word by replacing them with '*'. Then, convert to lowercase and store it in vowelMap.
State: vowelMap = { "k*t*" → "KiTe", "h*r*" → "Hare" }
Now, We will process Each Query
Now, let's process each query and check for matches in the order of precedence (exact match, case-insensitive match, vowel-error match).
Query 1: "kite"
Iteration 1:
Check for exact match. Check if "kite" is in exactMatches.
If found in exactMatches then return and we have our Result = ["kite"]
Query 2: "Kite"
Iteration 1: Check for exact match
Action: Check if "Kite" is in exactMatches.
Result: Not found.
Iteration 2: Check for case-insensitive match
Action: Convert "Kite" to lowercase ("kite") and check in caseInsensitiveMap.
Result: Found "kite" in caseInsensitiveMap → "KiTe".
State: Return "KiTe".
Current State: Result = ["kite", "KiTe"]
Query 3: "KiTe"
Iteration 1: Check for exact match
Action: Check if "KiTe" is in exactMatches.
Result: Found in exactMatches.
State: Return "KiTe".
Current State: Result = ["kite", "KiTe", "KiTe"]
Query 4: "Hare"
Iteration 1: Check for exact match
Action: Check if "Hare" is in exactMatches.
Result: Found in exactMatches.
State: Return "Hare".
Current State: Result = ["kite", "KiTe", "KiTe", "Hare"]
Query 5: "HARE"
Iteration 1: Check for exact match
Action: Check if "HARE" is in exactMatches.
Result: Not found.
Iteration 2: Check for case-insensitive matchAction: Convert "HARE" to lowercase ("hare") and check in caseInsensitiveMap.
Result: Found "hare" in caseInsensitiveMap → "hare".
State: Return "hare".
Current State: Result = ["kite", "KiTe", "KiTe", "Hare", "hare"]
Query 6: "Hear"
Iteration 1: Check for exact match
Action: Check if "Hear" is in exactMatches.
Result: Not found.
Iteration 2: Check for case-insensitive match
Action: Convert "Hear" to lowercase ("hear") and check in caseInsensitiveMap.
Result: Not found.
Iteration 3: Check for vowel-error match
Action: Normalize "Hear" to "Har" → "hr", and check in vowelMap.
Result: Not found.
State: Return "" (no match found).
Current State: Result = ["kite", "KiTe", "KiTe", "Hare", "hare", ""]
Query 7: "hear"
Iteration 1: Check for exact match
Action: Check if "hear" is in exactMatches.
Result: Not found.
Iteration 2: Check for case-insensitive match
Action: Convert "hear" to lowercase ("hear") and check in caseInsensitiveMap.
Result: Found "hear" in caseInsensitiveMap → "hare".
State: Return "hare".
Current State: Result = ["kite", "KiTe", "KiTe", "Hare", "hare", "", "hare"]
Query 8: "keti"
Iteration 1: Check for exact match
Action: Check if "keti" is in exactMatches.
Result: Not found.
Iteration 2: Check for case-insensitive match
Action: Convert "keti" to lowercase ("keti") and check in caseInsensitiveMap.
Result: Not found.
Iteration 3: Check for vowel-error match
Action: Normalize "keti" to "ket*" → "kt" and check in vowelMap.
Result: Not found.
State: Return "" (no match found).
Current State: Result = ["kite", "KiTe", "KiTe", "Hare", "hare", "", "hare", ""]
Query 9: "keet"
Iteration 1: Check for exact match
Action: Check if "keet" is in exactMatches.
Result: Not found.
Iteration 2: Check for case-insensitive match
Action: Convert "keet" to lowercase ("keet") and check in caseInsensitiveMap.
Result: Not found.
Iteration 3: Check for vowel-error match
Action: Normalize "keet" to "ket*" → "kt" and check in vowelMap.
Result: Not found.
State: Return "" (no match found).
Current State: Result = ["kite", "KiTe", "KiTe", "Hare", "hare", "", "hare", "", ""]
Query 10: "keto"
Iteration 1: Check for exact match
Action: Check if "keto" is in exactMatches.
Result: Not found.
Iteration 2: Check for case-insensitive match
Action: Convert "keto" to lowercase ("keto") and check in caseInsensitiveMap.
Result: Not found.
Iteration 3: Check for vowel-error match
Action: Normalize "keto" to "ket*" → "kt" and check in vowelMap.
Result: Not found.
State: Return "" (no match found).
Current State: Result = ["kite", "KiTe", "KiTe", "Hare", "hare", "", "hare", "", "", ""]
Final Output:
["kite", "KiTe", "KiTe", "Hare", "hare", "", "hare", "", "", ""]
Dry Run
Input: chars = ['a', 'a', 'b', 'b', 'b', 'c', 'c']
Output: 6 (chars = ['a', '2', 'b', '3', 'c', '2'])
Explanation: Count of 'a' is 2, so we compress it to ['a', '2']. Count of 'b' is 3, so we compress it to ['b', '3']. Count of 'c' is 2, so we compress it to ['c', '2'].
Initial Setup
- n = 7 (size of chars).
- itr = 0 (iterator to traverse the chars array).
- compressedString = [] (to temporarily store the compressed groups).
Step 1: First While Loop
1st Iteration (Character: 'a')
- Initialization: grpSize = 1 (group size starts with 1).
- Inner While Loop: Condition: itr + grpSize < n (0 + 1 < 7) and chars[itr + grpSize] == chars[itr] ('a' == 'a').
- Increment grpSize: grpSize = 2.
- Store Group: Add group {'a', 2} to compressedString: compressedString = [{'a', 2}].
- Update Iterator: itr += grpSize → itr = 2.
2nd Iteration (Character: 'b')
- Initialization: grpSize = 1.
- Inner While Loop:
Condition: itr + grpSize < n (2 + 1 < 7) and chars[itr + grpSize] == chars[itr] ('b' == 'b').
Increment grpSize: grpSize = 2.
Repeat: itr + grpSize < n (2 + 2 < 7) and chars[itr + grpSize] == chars[itr] ('b' == 'b'). Increment grpSize: grpSize = 3.
- Store Group: Add group {'b', 3} to compressedString: compressedString = [{'a', 2}, {'b', 3}].
- Update Iterator: itr += grpSize → itr = 5.
3rd Iteration (Character: 'c')
- Initialization: grpSize = 1.
- Inner While Loop: Condition: itr + grpSize < n (5 + 1 < 7) and chars[itr + grpSize] == chars[itr] ('c' == 'c').
- Increment grpSize: grpSize = 2.
- Store Group: Add group {'c', 2} to compressedString: compressedString = [{'a', 2}, {'b', 3}, {'c', 2}].
- Update Iterator: itr += grpSize → itr = 7.
Compressed Groups After First Loop compressedString = [{'a', 2}, {'b', 3}, {'c', 2}].
Step 2: Second Loop (Updating chars) Initialization: idx = 0 (pointer to write the compressed characters into chars).
1st Group (Character: 'a', Count: 2)
- Write 'a' at chars[idx]: chars = ['a', 'a', 'b', 'b', 'b', 'c', 'c'], idx = 1.
- Count is greater than 1, so convert 2 to string ("2") and write it: Write '2' at chars[idx]: chars = ['a', '2', 'b', 'b', 'b', 'c', 'c'], idx = 2.
2nd Group (Character: 'b', Count: 3)
- Write 'b' at chars[idx]: chars = ['a', '2', 'b', 'b', 'b', 'c', 'c'], idx = 3.
- Count is greater than 1, so convert 3 to string ("3") and write it: Write '3' at chars[idx]: chars = ['a', '2', 'b', '3', 'b', 'c', 'c'], idx = 4.
3rd Group (Character: 'c', Count: 2)
- Write 'c' at chars[idx]: chars = ['a', '2', 'b', '3', 'c', 'c', 'c'], idx = 5.
- Count is greater than 1, so convert 2 to string ("2") and write it: Write '2' at chars[idx]: chars = ['a', '2', 'b', '3', 'c', '2', 'c'], idx = 6.
Final Output
- Compressed chars = ['a', '2', 'b', '3', 'c', '2'].
- idx = 6 (length of the compressed string).
Return Value: 6.
Code for All Languages
C++
class Solution {
public:
// Vowel Spellchecker solution in C++
// Helper function to check if a character is a vowel
bool isVowel(char c) {
c = tolower(c);
return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
}
// Helper function to normalize vowels in a word (replace vowels with '*')
string normalizeVowels(string word) {
for (char &c : word) {
// Replace vowels with '*' to normalize the word
if (isVowel(c)) {
c = '*';
}
}
return word;
}
vector<string> spellchecker(vector<string>& wordlist, vector<string>& queries) {
// Create a set for exact word matches
unordered_set<string> exactMatches(wordlist.begin(), wordlist.end());
// Create a map for case-insensitive matches (lowercase version of words)
unordered_map<string, string> caseInsensitiveMap;
for (const string &word : wordlist) {
string lowerWord = word;
// Convert word to lowercase to handle case-insensitive matching
transform(lowerWord.begin(), lowerWord.end(), lowerWord.begin(), ::tolower);
// Store the first occurrence of the lowercase word in the map
if (caseInsensitiveMap.find(lowerWord) == caseInsensitiveMap.end()) {
caseInsensitiveMap[lowerWord] = word;
}
}
// Create a map for vowel-normalized matches (replacing vowels with '*')
unordered_map<string, string> vowelMap;
for (const string &word : wordlist) {
string vowelWord = normalizeVowels(word);
// Convert the normalized word to lowercase
transform(vowelWord.begin(), vowelWord.end(), vowelWord.begin(), ::tolower);
// Store the first occurrence of the vowel-normalized word in the map
if (vowelMap.find(vowelWord) == vowelMap.end()) {
vowelMap[vowelWord] = word;
}
}
vector<string> result;
// Process each query
for (const string &query : queries) {
// 1. Exact match: Check if the query exists exactly in the set
if (exactMatches.find(query) != exactMatches.end()) {
result.push_back(query);
continue;
}
// 2. Case-insensitive match: Convert the query to lowercase and check the map
string lowerQuery = query;
transform(lowerQuery.begin(), lowerQuery.end(), lowerQuery.begin(), ::tolower);
if (caseInsensitiveMap.find(lowerQuery) != caseInsensitiveMap.end()) {
result.push_back(caseInsensitiveMap[lowerQuery]);
continue;
}
// 3. Vowel error match: Normalize vowels in the query and check the map
string vowelQuery = normalizeVowels(query);
transform(vowelQuery.begin(), vowelQuery.end(), vowelQuery.begin(), ::tolower);
if (vowelMap.find(vowelQuery) != vowelMap.end()) {
result.push_back(vowelMap[vowelQuery]);
continue;
}
// 4. No match: If no matches are found, add an empty string to the result
result.push_back("");
}
return result;
}
};Java
import java.util.*;
class Solution {
// Vowel Spellchecker solution in Java
// Helper function to check if a character is a vowel
private boolean isVowel(char c) {
c = Character.toLowerCase(c);
return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
}
// Helper function to normalize vowels in a word (replace vowels with '*')
private String normalizeVowels(String word) {
StringBuilder normalized = new StringBuilder(word);
for (int i = 0; i < word.length(); i++) {
if (isVowel(word.charAt(i))) {
normalized.setCharAt(i, '*');
}
}
return normalized.toString();
}
public String[] spellchecker(String[] wordlist, String[] queries) {
// Create a set for exact word matches
Set<String> exactMatches = new HashSet<>(Arrays.asList(wordlist));
// Create a map for case-insensitive matches (lowercase version of words)
Map<String, String> caseInsensitiveMap = new HashMap<>();
for (String word : wordlist) {
String lowerWord = word.toLowerCase();
caseInsensitiveMap.putIfAbsent(lowerWord, word);
}
// Create a map for vowel-normalized matches (replacing vowels with '*')
Map<String, String> vowelMap = new HashMap<>();
for (String word : wordlist) {
String vowelWord = normalizeVowels(word);
vowelMap.putIfAbsent(vowelWord.toLowerCase(), word);
}
String[] result = new String[queries.length];
// Process each query
for (int i = 0; i < queries.length; i++) {
String query = queries[i];
// 1. Exact match
if (exactMatches.contains(query)) {
result[i] = query;
continue;
}
// 2. Case-insensitive match
String lowerQuery = query.toLowerCase();
if (caseInsensitiveMap.containsKey(lowerQuery)) {
result[i] = caseInsensitiveMap.get(lowerQuery);
continue;
}
// 3. Vowel error match
String vowelQuery = normalizeVowels(query).toLowerCase();
if (vowelMap.containsKey(vowelQuery)) {
result[i] = vowelMap.get(vowelQuery);
continue;
}
// 4. No match
result[i] = "";
}
return result;
}
}Python
class Solution:
# Vowel Spellchecker solution in Python
# Helper function to check if a character is a vowel
def isVowel(self, c):
c = c.lower()
return c in 'aeiou'
# Helper function to normalize vowels in a word (replace vowels with '*')
def normalizeVowels(self, word):
return ''.join('*' if self.isVowel(c) else c for c in word)
def spellchecker(self, wordlist, queries):
# Create a set for exact word matches
exactMatches = set(wordlist)
# Create a map for case-insensitive matches (lowercase version of words)
caseInsensitiveMap = {}
for word in wordlist:
lowerWord = word.lower()
caseInsensitiveMap.setdefault(lowerWord, word)
# Create a map for vowel-normalized matches (replacing vowels with '*')
vowelMap = {}
for word in wordlist:
vowelWord = self.normalizeVowels(word)
vowelMap.setdefault(vowelWord.lower(), word)
result = []
# Process each query
for query in queries:
# 1. Exact match
if query in exactMatches:
result.append(query)
continue
# 2. Case-insensitive match
lowerQuery = query.lower()
if lowerQuery in caseInsensitiveMap:
result.append(caseInsensitiveMap[lowerQuery])
continue
# 3. Vowel error match
vowelQuery = self.normalizeVowels(query).lower()
if vowelQuery in vowelMap:
result.append(vowelMap[vowelQuery])
continue
# 4. No match
result.append("")
return resultJavascript
class Solution {
// Vowel Spellchecker solution in JavaScript
// Helper function to check if a character is a vowel
isVowel(c) {
c = c.toLowerCase();
return 'aeiou'.includes(c);
}
// Helper function to normalize vowels in a word (replace vowels with '*')
normalizeVowels(word) {
return word.split('').map(c => this.isVowel(c) ? '*' : c).join('');
}
spellchecker(wordlist, queries) {
// Create a set for exact word matches
const exactMatches = new Set(wordlist);
// Create a map for case-insensitive matches (lowercase version of words)
const caseInsensitiveMap = {};
for (let word of wordlist) {
const lowerWord = word.toLowerCase();
if (!(lowerWord in caseInsensitiveMap)) {
caseInsensitiveMap[lowerWord] = word;
}
}
// Create a map for vowel-normalized matches (replacing vowels with '*')
const vowelMap = {};
for (let word of wordlist) {
const vowelWord = this.normalizeVowels(word);
vowelMap[vowelWord.toLowerCase()] = word;
}
const result = [];
// Process each query
for (let query of queries) {
// 1. Exact match
if (exactMatches.has(query)) {
result.push(query);
continue;
}
// 2. Case-insensitive match
const lowerQuery = query.toLowerCase();
if (lowerQuery in caseInsensitiveMap) {
result.push(caseInsensitiveMap[lowerQuery]);
continue;
}
// 3. Vowel error match
const vowelQuery = this.normalizeVowels(query).toLowerCase();
if (vowelQuery in vowelMap) {
result.push(vowelMap[vowelQuery]);
continue;
}
// 4. No match
result.push("");
}
return result;
}
}Time Complexity: O(n * m + q * m)
We are building three data structures for processing the queries. First is exactMatches (HashSet): This is created using the wordlist. It takes O(n) time where n is the length of wordlist.
Then caseInsensitiveMap (HashMap) for each word in the wordlist, we convert it to lowercase (which takes O(m) time, where m is the maximum length of a word), and then store it in the map. Therefore, constructing this map takes O(n * m) time.
For vowelMap (HashMap), each word in the wordlist, we normalize vowels (which again takes O(m) time per word) and store it in the map. This also takes O(n * m) time.
Processing the Queries:
For each query, we do three checks,
Exact match check: This takes O(1) time because we’re just looking for the query in the exactMatches set.
For Case-insensitive match check, we convert the query to lowercase (which takes O(m) time) and check the map. Vowel error match check in the query (this takes O(m) time) and then check the map.
So, for each query, we spend O(m) time doing these checks. Since there are q queries, the total time spent processing all the queries is O(q * m).
So, Overall Time Complexity when you add everything up, the total time complexity becomes O(n * m + q * m). This includes the time for setting up the maps and processing all the queries.
Space Complexity: O(n*m + q)
We need to consider how much space we’re using for the different data structures. For data structure exact matches (exactMatches), we store all the words in a HashSet, so it takes O(n) space, where n is the number of words in the wordlist.
For Case-insensitive Matches (caseInsensitiveMap), map stores the lowercase version of each word, so it needs O(n * m) space, where m is the maximum length of any word. We’re storing n words, and each word is a string of length m.
We store the results for all the queries in an array, which requires O(q) space, where q is the number of queries.
Hence, Overall Space Complexity, when we add up all the space used by the data structures, the total space complexity is O(n * m + q). This is because we need space for all the words in the wordlist, the results for the queries, and the auxiliary data structures.
Learning Tip
Now that we've successfully tackled this problem, let's try these similar problems to further enhance your understanding:
Given two strings s and t, determine if t is an anagram of s. An anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.
Given a string s, determine if a permutation of the string could form a palindrome. A palindrome is a word or phrase that reads the same backward as forward. Similar to this question is "sort vowels in a string" in Leetcode.