Vowel Spellchecker — Solution in Python, Java & C++
Vowel Spellchecker solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem on arrays and strings.
Vowel Spellchecker is a medium coding problem on arrays, strings and hash table, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Arrays, Strings, Hash Table
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Build a spellchecker over a dictionary wordlist. For each word in queries, return the dictionary word it corrects to, applying these rules in order of precedence:
- Exact match — the query is in
wordlistexactly (same case): return the query itself. - Capitalisation — the query equals some dictionary word when both are lowercased: return the first such word in
wordlist. - Vowel errors — after lowercasing both, the query equals some dictionary word if each vowel (
a,e,i,o,u) may be swapped for any vowel in place: return the first such word inwordlist. - Otherwise return the empty string
"".
Return the list of corrections, one per query, in query order.
Example 1
Input: wordlist = ["Apple","apply","Orange"], queries = ["apple","APPLY","Apple","upplo","orangi","pear"]
Output: ["Apple","apply","Apple","Apple","Orange",""]
Explanation: `apple` matches `Apple` ignoring case. `upplo` matches `Apple` up to vowels (`*ppl*`) — `apply` ends in `y`, which is not a vowel. Nothing resembles `pear`.
Example 2
Input: wordlist = ["yellow"], queries = ["YellOw","yollow","yeellow"]
Output: ["yellow","yellow",""]
Explanation: A vowel can be swapped but not inserted, so `yeellow` matches nothing.
Constraints
1 <= wordlist.length, queries.length <= 50001 <= wordlist[i].length, queries[i].length <= 7wordlist[i] and queries[i] hold English letters only
Hints for Vowel Spellchecker
Hint 1
Each rule is a lookup on a different normal form of the word: as-is, lowercased, and lowercased with vowels masked.
Hint 2
Precompute three tables from the dictionary: a set of exact words, and two maps from a normal form to the first dictionary word with that form.
Hint 3
When filling the maps, only insert a key the first time you see it, so the earliest dictionary word wins.
How to solve Vowel Spellchecker
Normalise words two ways — lowercase, and lowercase with every vowel replaced by * — and the three matching rules become three hash lookups, tried in precedence order.
Approach
- Put every dictionary word in an exact-match set.
- For each dictionary word in order, insert
lower(w) → wanddevowel(lower(w)) → winto two maps, only if the key is not already present. - For each query: if it is in the exact set, answer it; else if
lower(q)is in the first map, answer that; else ifdevowel(lower(q))is in the second map, answer that; else answer"".
Why it works
Two words match under rule 2 exactly when their lowercase forms are equal, and under rule 3 exactly when their masked forms are equal (vowels are only swapped in place, so lengths and consonant positions must agree). Keeping the first insertion per key yields the first dictionary word for that form, and checking the rules in order applies the precedence.
Complexity
- Time —
O((W + Q) · L) - Space —
O(W · L)
Pitfalls
- Rule 1 is case-sensitive:
ApplematchesAppleexactly, butappleis not an exact match for it. - Overwriting map entries makes the last dictionary word win instead of the first.
- Only vowels are masked —
yis a consonant here.
Reference solution
Python
from typing import List
def spellchecker(wordlist: List[str], queries: List[str]) -> List[str]:
def devowel(s):
return ''.join('*' if c in 'aeiou' else c for c in s)
exact = set(wordlist)
by_case = {}
by_vowel = {}
for w in wordlist:
low = w.lower()
by_case.setdefault(low, w)
by_vowel.setdefault(devowel(low), w)
out = []
for q in queries:
if q in exact:
out.append(q)
continue
low = q.lower()
if low in by_case:
out.append(by_case[low])
else:
out.append(by_vowel.get(devowel(low), ''))
return outJava
public static String[] spellchecker(String[] wordlist, String[] queries) {
Set<String> exact = new HashSet<>(Arrays.asList(wordlist));
Map<String, String> byCase = new HashMap<>();
Map<String, String> byVowel = new HashMap<>();
for (String w : wordlist) {
String low = w.toLowerCase();
byCase.putIfAbsent(low, w);
byVowel.putIfAbsent(devowel(low), w);
}
String[] out = new String[queries.length];
for (int i = 0; i < queries.length; i++) {
String q = queries[i];
if (exact.contains(q)) { out[i] = q; continue; }
String low = q.toLowerCase();
if (byCase.containsKey(low)) { out[i] = byCase.get(low); continue; }
out[i] = byVowel.getOrDefault(devowel(low), "");
}
return out;
}
private static String devowel(String s) {
char[] a = s.toCharArray();
for (int i = 0; i < a.length; i++) if ("aeiou".indexOf(a[i]) >= 0) a[i] = '*';
return new String(a);
}C++
static string devowelOf(const string& s) {
string r = s;
for (char& c : r) if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u') c = '*';
return r;
}
static string lowerOf(const string& s) {
string r = s;
for (char& c : r) c = (char)tolower((unsigned char)c);
return r;
}
vector<string> spellchecker(vector<string>& wordlist, vector<string>& queries) {
unordered_set<string> exact(wordlist.begin(), wordlist.end());
unordered_map<string, string> byCase, byVowel;
for (const string& w : wordlist) {
string low = lowerOf(w);
byCase.emplace(low, w);
byVowel.emplace(devowelOf(low), w);
}
vector<string> out;
for (const string& q : queries) {
if (exact.count(q)) { out.push_back(q); continue; }
string low = lowerOf(q);
auto it = byCase.find(low);
if (it != byCase.end()) { out.push_back(it->second); continue; }
auto jt = byVowel.find(devowelOf(low));
out.push_back(jt != byVowel.end() ? jt->second : "");
}
return out;
}JavaScript
var spellchecker = function(wordlist, queries) {
var devowel = function(s) { return s.replace(/[aeiou]/g, '*'); };
var exact = new Set(wordlist);
var byCase = new Map(), byVowel = new Map();
for (var i = 0; i < wordlist.length; i++) {
var low = wordlist[i].toLowerCase();
if (!byCase.has(low)) byCase.set(low, wordlist[i]);
var dv = devowel(low);
if (!byVowel.has(dv)) byVowel.set(dv, wordlist[i]);
}
var out = [];
for (var j = 0; j < queries.length; j++) {
var q = queries[j];
if (exact.has(q)) { out.push(q); continue; }
var lq = q.toLowerCase();
if (byCase.has(lq)) { out.push(byCase.get(lq)); continue; }
var dq = devowel(lq);
out.push(byVowel.has(dq) ? byVowel.get(dq) : '');
}
return out;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.