Vowel Spellchecker

medium hash map string

Problem

Given a wordlist, implement a spellchecker that converts each query word to a correct word. For a query, check matches in priority order: (1) exact match (case-sensitive) returns the query itself; (2) case-insensitive match returns the first such wordlist word; (3) vowel-error match — where vowels a, e, i, o, u may be swapped for one another — returns the first such wordlist word. If none match, return the empty string.

Inputwordlist = ["Yellow", "hello", "hEllo"], queries = ["yollow", "HELLO", "help"]

Output["Yellow", "hello", ""]

"yollow" matches "Yellow" by vowel pattern; "HELLO" matches "hello" case-insensitively; "help" matches nothing.

wordlist (comma-separated)

query word

def spellchecker(wordlist, queries):
    exact = set(wordlist)
    cap, vow = {}, {}

    def devowel(w):
        return "".join("*" if c in "aeiou" else c for c in w.lower())

    for w in wordlist:
        cap.setdefault(w.lower(), w)
        vow.setdefault(devowel(w), w)

    def solve(q):
        if q in exact:
            return q
        low = q.lower()
        if low in cap:
            return cap[low]
        dv = devowel(q)
        if dv in vow:
            return vow[dv]
        return ""

    return [solve(q) for q in queries]

function spellchecker(wordlist, queries) {
  const exact = new Set(wordlist);
  const cap = new Map(), vow = new Map();
  const devowel = w => w.toLowerCase().replace(/[aeiou]/g, "*");

  for (const w of wordlist) {
    const lo = w.toLowerCase(), dv = devowel(w);
    if (!cap.has(lo)) cap.set(lo, w);
    if (!vow.has(dv)) vow.set(dv, w);
  }

  return queries.map(q => {
    if (exact.has(q)) return q;
    const lo = q.toLowerCase();
    if (cap.has(lo)) return cap.get(lo);
    const dv = devowel(q);
    if (vow.has(dv)) return vow.get(dv);
    return "";
  });
}

class Solution {
    public String[] spellchecker(String[] wordlist, String[] queries) {
        Set<String> exact = new HashSet<>(Arrays.asList(wordlist));
        Map<String, String> cap = new HashMap<>(), vow = new HashMap<>();
        for (String w : wordlist) {
            String lo = w.toLowerCase();
            cap.putIfAbsent(lo, w);
            vow.putIfAbsent(devowel(lo), w);
        }
        String[] res = new String[queries.length];
        for (int i = 0; i < queries.length; i++) {
            String q = queries[i], lo = q.toLowerCase();
            if (exact.contains(q)) res[i] = q;
            else if (cap.containsKey(lo)) res[i] = cap.get(lo);
            else if (vow.containsKey(devowel(lo))) res[i] = vow.get(devowel(lo));
            else res[i] = "";
        }
        return res;
    }
    private String devowel(String w) {
        return w.replaceAll("[aeiou]", "*");
    }
}

class Solution {
public:
    string devowel(string w) {
        for (char &c : w) {
            c = tolower(c);
            if (c=='a'||c=='e'||c=='i'||c=='o'||c=='u') c = '*';
        }
        return w;
    }
    vector<string> spellchecker(vector<string>& wordlist, vector<string>& queries) {
        unordered_set<string> exact(wordlist.begin(), wordlist.end());
        unordered_map<string, string> cap, vow;
        for (auto &w : wordlist) {
            string lo = w; for (char &c : lo) c = tolower(c);
            cap.insert({lo, w});
            vow.insert({devowel(w), w});
        }
        vector<string> res;
        for (auto &q : queries) {
            string lo = q; for (char &c : lo) c = tolower(c);
            if (exact.count(q)) res.push_back(q);
            else if (cap.count(lo)) res.push_back(cap[lo]);
            else if (vow.count(devowel(q))) res.push_back(vow[devowel(q)]);
            else res.push_back("");
        }
        return res;
    }
};

Explanation

The spellchecker has to try three kinds of match in priority order: exact, case-insensitive, then vowel-swapped. The smart move is to precompute three lookup tables once, so every query is answered with fast hash lookups instead of scanning the whole wordlist each time.

We build a set exact of the original words, a map cap from each word's lowercase form to the original, and a map vow from each word's vowel-blanked form to the original. The helper devowel lowercases the word and replaces every vowel with *, so "hello" and "hallo" both become "h*ll*". We use setdefault so the first wordlist entry wins on ties.

To answer a query q we cascade: if q in exact return q as-is; else if its lowercase is in cap return that stored word; else if its devoweled form is in vow return that word; otherwise return the empty string.

Example: with wordlist ["Yellow", "hello", "hEllo"], the query "yollow" is not exact and not in cap, but devowel("yollow") = "y*ll*w" matches "Yellow", so it returns "Yellow". The query "HELLO" hits cap["hello"] and returns "hello", while "help" matches nothing and returns "".

Building the tables is linear in the wordlist, and each query is then resolved in time proportional to the word's length, which is why this scales well.

Time: O(N + Q·L) Space: O(N·L)