Vowel Spellchecker

Medium
1782.

Vowel Spellchecker

Vowel Spellchecker is a medium coding problem on arrays, strings and hash table, asked in Amazon and Google interviews.

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:

  1. Exact match — the query is in wordlist exactly (same case): return the query itself.
  2. Capitalisation — the query equals some dictionary word when both are lowercased: return the first such word in wordlist.
  3. 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 in wordlist.
  4. 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 <= 5000
  • 1 <= wordlist[i].length, queries[i].length <= 7
  • wordlist[i] and queries[i] hold English letters only
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string[]} wordlist
 * @param {string[]} queries
 * @return {string[]}
 */
var spellchecker = function(wordlist, queries) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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:

  1. Exact match — the query is in wordlist exactly (same case): return the query itself.
  2. Capitalisation — the query equals some dictionary word when both are lowercased: return the first such word in wordlist.
  3. 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 in wordlist.
  4. 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 <= 5000
  • 1 <= wordlist[i].length, queries[i].length <= 7
  • wordlist[i] and queries[i] hold English letters only

Hints for Vowel Spellchecker

  1. Hint 1

    Each rule is a lookup on a different normal form of the word: as-is, lowercased, and lowercased with vowels masked.

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

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

  1. Put every dictionary word in an exact-match set.
  2. For each dictionary word in order, insert lower(w) → w and devowel(lower(w)) → w into two maps, only if the key is not already present.
  3. For each query: if it is in the exact set, answer it; else if lower(q) is in the first map, answer that; else if devowel(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: Apple matches Apple exactly, but apple is not an exact match for it.
  • Overwriting map entries makes the last dictionary word win instead of the first.
  • Only vowels are masked — y is 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 out

Java

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.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Strings