Vowel Spellchecker

Problem

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].

Examples

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 <= 5000
• 1 <= wordlist[i].length, queries[i].length <= 7
• wordlist[i] and queries[i] consist only of only English letters.

Solution

Method 1 – Hash Maps and Vowel Masking

Intuition

Use hash maps to store exact, case-insensitive, and vowel-masked versions of the wordlist for fast lookup. For each query, check in order: exact match, case-insensitive match, vowel-error match.

Approach

1. Build three maps:
   • Exact words (set)
   • Lowercase words (first occurrence)
   • Vowel-masked words (first occurrence)
2. For each query, check in order: exact, lowercase, vowel-masked.

Code

C++

#include <vector>
#include <string>
#include <unordered_set>
#include <unordered_map>
using namespace std;
string devowel(const string& w) {
    string res = w;
    for (char& c : res) if (string("aeiouAEIOU").find(c) != string::npos) c = '*';
    return res;
}
class Solution {
public:
    vector<string> spellchecker(vector<string>& wordlist, vector<string>& queries) {
        unordered_set<string> exact(wordlist.begin(), wordlist.end());
        unordered_map<string, string> lower, vowel;
        for (const string& w : wordlist) {
            string wl = w;
            for (auto& c : wl) c = tolower(c);
            if (!lower.count(wl)) lower[wl] = w;
            string vw = devowel(wl);
            if (!vowel.count(vw)) vowel[vw] = w;
        }
        vector<string> res;
        for (const string& q : queries) {
            if (exact.count(q)) res.push_back(q);
            else {
                string ql = q;
                for (auto& c : ql) c = tolower(c);
                if (lower.count(ql)) res.push_back(lower[ql]);
                else {
                    string vq = devowel(ql);
                    if (vowel.count(vq)) res.push_back(vowel[vq]);
                    else res.push_back("");
                }
            }
        }
        return res;
    }
};

Go

import "strings"
func devowel(w string) string {
    res := []rune(w)
    for i, c := range res {
        if strings.ContainsRune("aeiouAEIOU", c) {
            res[i] = '*'
        }
    }
    return string(res)
}
func spellchecker(wordlist []string, queries []string) []string {
    exact := make(map[string]struct{})
    lower := make(map[string]string)
    vowel := make(map[string]string)
    for _, w := range wordlist {
        wl := strings.ToLower(w)
        if _, ok := lower[wl]; !ok {
            lower[wl] = w
        }
        vw := devowel(wl)
        if _, ok := vowel[vw]; !ok {
            vowel[vw] = w
        }
        exact[w] = struct{}{}
    }
    res := make([]string, len(queries))
    for i, q := range queries {
        if _, ok := exact[q]; ok {
            res[i] = q
        } else if v, ok := lower[strings.ToLower(q)]; ok {
            res[i] = v
        } else if v, ok := vowel[devowel(strings.ToLower(q))]; ok {
            res[i] = v
        } else {
            res[i] = ""
        }
    }
    return res
}

Java

import java.util.*;
class Solution {
    public String[] spellchecker(String[] wordlist, String[] queries) {
        Set<String> exact = new HashSet<>(Arrays.asList(wordlist));
        Map<String, String> lower = new HashMap<>();
        Map<String, String> vowel = new HashMap<>();
        for (String w : wordlist) {
            String wl = w.toLowerCase();
            lower.putIfAbsent(wl, w);
            String vw = devowel(wl);
            vowel.putIfAbsent(vw, w);
        }
        String[] res = new String[queries.length];
        for (int i = 0; i < queries.length; i++) {
            String q = queries[i];
            if (exact.contains(q)) res[i] = q;
            else if (lower.containsKey(q.toLowerCase())) res[i] = lower.get(q.toLowerCase());
            else if (vowel.containsKey(devowel(q.toLowerCase()))) res[i] = vowel.get(devowel(q.toLowerCase()));
            else res[i] = "";
        }
        return res;
    }
    private String devowel(String w) {
        StringBuilder sb = new StringBuilder();
        for (char c : w.toCharArray()) {
            sb.append("aeiou".indexOf(c) >= 0 ? '*' : c);
        }
        return sb.toString();
    }
}

Kotlin

class Solution {
    fun spellchecker(wordlist: Array<String>, queries: Array<String>): Array<String> {
        fun devowel(w: String) = w.lowercase().map { if (it in "aeiou") '*' else it }.joinToString("")
        val exact = wordlist.toSet()
        val lower = mutableMapOf<String, String>()
        val vowel = mutableMapOf<String, String>()
        for (w in wordlist) {
            val wl = w.lowercase()
            lower.putIfAbsent(wl, w)
            val vw = devowel(w)
            vowel.putIfAbsent(vw, w)
        }
        return queries.map { q ->
            when {
                q in exact -> q
                lower.containsKey(q.lowercase()) -> lower[q.lowercase()]!!
                vowel.containsKey(devowel(q)) -> vowel[devowel(q)]!!
                else -> ""
            }
        }.toTypedArray()
    }
}

Python

from typing import List
class Solution:
    def spellchecker(self, wordlist: List[str], queries: List[str]) -> List[str]:
        def devowel(word):
            return ''.join('*' if c in 'aeiou' else c for c in word.lower())
        exact = set(wordlist)
        lower = {}
        vowel = {}
        for w in wordlist:
            wl = w.lower()
            if wl not in lower:
                lower[wl] = w
            vw = devowel(w)
            if vw not in vowel:
                vowel[vw] = w
        res = []
        for q in queries:
            if q in exact:
                res.append(q)
            elif q.lower() in lower:
                res.append(lower[q.lower()])
            elif devowel(q) in vowel:
                res.append(vowel[devowel(q)])
            else:
                res.append("")
        return res

Rust

use std::collections::{HashSet, HashMap};
fn devowel(w: &str) -> String {
    w.chars().map(|c| if "aeiouAEIOU".contains(c) { '*' } else { c }).collect()
}
pub fn spellchecker(wordlist: Vec<String>, queries: Vec<String>) -> Vec<String> {
    let exact: HashSet<_> = wordlist.iter().cloned().collect();
    let mut lower = HashMap::new();
    let mut vowel = HashMap::new();
    for w in &wordlist {
        let wl = w.to_lowercase();
        lower.entry(wl.clone()).or_insert(w.clone());
        let vw = devowel(&wl);
        vowel.entry(vw).or_insert(w.clone());
    }
    queries.iter().map(|q| {
        if exact.contains(q) {
            q.clone()
        } else if let Some(w) = lower.get(&q.to_lowercase()) {
            w.clone()
        } else if let Some(w) = vowel.get(&devowel(&q.to_lowercase())) {
            w.clone()
        } else {
            String::new()
        }
    }).collect()
}

TypeScript

function devowel(w: string): string {
    return w.toLowerCase().replace(/[aeiou]/g, '*');
}
function spellchecker(wordlist: string[], queries: string[]): string[] {
    const exact = new Set(wordlist);
    const lower = new Map<string, string>();
    const vowel = new Map<string, string>();
    for (const w of wordlist) {
        const wl = w.toLowerCase();
        if (!lower.has(wl)) lower.set(wl, w);
        const vw = devowel(wl);
        if (!vowel.has(vw)) vowel.set(vw, w);
    }
    return queries.map(q => {
        if (exact.has(q)) return q;
        const ql = q.toLowerCase();
        if (lower.has(ql)) return lower.get(ql)!;
        const vq = devowel(ql);
        if (vowel.has(vq)) return vowel.get(vq)!;
        return "";
    });
}

Complexity

• ⏰ Time complexity: O(N + Q * L) — N = wordlist size, Q = queries size, L = word length (≤7).
• 🧺 Space complexity: O(N * L) — For the hash maps.