Vowel Spellchecker - Practice Coding Problems

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"

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"

The spell checker operates under the following precedence rules:

1. When the query exactly matches a word in the wordlist (case-sensitive), return the same word back.

2. When the query matches a word up to capitalization, return the first such match in the wordlist.

3. When the query matches a word up to vowel errors, return the first such match in the wordlist.

4. If the query has no matches in the wordlist, return the empty string.

Given some queries, return a list of words answer, where answer[i] is the correct word for query = queries[i].

Input & Output

Example 1 — Mixed Cases and Vowel Errors

$ Input: wordlist = ["KiTe", "kite", "hare", "Hare"], queries = ["kite", "Kite", "KiTe", "Hare", "HARE", "Hear", "hear", "keti"]

› Output: ["kite", "KiTe", "KiTe", "Hare", "hare", "", "", "KiTe"]

💡 Note: "kite": exact match. "Kite": case match with "KiTe" (first). "KiTe": exact match. "Hare": exact match. "HARE": case match with "hare". "Hear": no vowel match. "hear": no match. "keti": vowel match with "KiTe".

Example 2 — Priority Testing

$ Input: wordlist = ["yellow", "Yellow", "YellOw"], queries = ["yellow", "Yellow", "YellOw"]

› Output: ["yellow", "Yellow", "YellOw"]

💡 Note: All queries have exact matches in the wordlist, so they return themselves unchanged.

Example 3 — No Matches

$ Input: wordlist = ["hello"], queries = ["hi", "world", "test"]

› Output: ["", "", ""]

💡 Note: None of the queries match "hello" exactly, by case, or by vowel pattern, so all return empty strings.

Constraints

1 ≤ wordlist.length, queries.length ≤ 5000
1 ≤ wordlist[i].length, queries[i].length ≤ 7
wordlist[i] and queries[i] consist only of English letters

Visualization

Tap to expand

Understanding the Visualization

Input

Wordlist and queries to be spell-checked

Priority Matching

Check exact → case → vowel pattern matches

Output

Corrected words or empty strings

Key Takeaway

🎯 Key Insight: Preprocess the dictionary into hash maps for each error type to achieve O(1) lookups instead of scanning the entire wordlist for each query.

Asked in

G Google 15 f Facebook 12 A Apple 8

The key insight is to preprocess the wordlist into hash maps for each match type (exact, case-insensitive, vowel pattern) to enable O(1) lookups. Best approach uses hash map optimization with Time: O(m×k + n×k), Space: O(m×k).

Common Approaches

Approach	Time	Space	Notes
✓ Hash Map Optimization	O(m × k + n × k)	O(m × k)	Preprocess wordlist into hash maps for instant lookups
Brute Force	O(n × m × k)	O(1)	For each query, check all words in wordlist for exact, case, and vowel matches

Hash Map Optimization — Algorithm Steps

Build hash map for exact word matches
Build hash map for lowercase patterns
Build hash map for vowel-normalized patterns
For each query, lookup in priority order

Visualization

Tap to expand

Step-by-Step Walkthrough

Preprocessing

Build 3 hash maps from wordlist

Query Processing

Instant O(1) lookups for each query

Priority Check

Check maps in order: exact → case → vowel

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

#define MAX_WORDS 1000
#define MAX_QUERIES 1000
#define MAX_LEN 100

struct HashMap {
    char keys[MAX_WORDS][MAX_LEN];
    char values[MAX_WORDS][MAX_LEN];
    int size;
};

void addToMap(struct HashMap* map, const char* key, const char* value) {
    for (int i = 0; i < map->size; i++) {
        if (strcmp(map->keys[i], key) == 0) {
            return; // Key already exists, keep first occurrence
        }
    }
    strcpy(map->keys[map->size], key);
    strcpy(map->values[map->size], value);
    map->size++;
}

char* findInMap(struct HashMap* map, const char* key) {
    for (int i = 0; i < map->size; i++) {
        if (strcmp(map->keys[i], key) == 0) {
            return map->values[i];
        }
    }
    return NULL;
}

void normalizeVowels(const char* word, char* result) {
    int len = strlen(word);
    for (int i = 0; i < len; i++) {
        char c = tolower(word[i]);
        if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u') {
            result[i] = '*';
        } else {
            result[i] = c;
        }
    }
    result[len] = '\0';
}

char** solution(char** wordlist, int wordlistSize, char** queries, int queriesSize, int* returnSize) {
    struct HashMap exactMap = {.size = 0};
    struct HashMap caseMap = {.size = 0};
    struct HashMap vowelMap = {.size = 0};
    
    // Build hash maps
    for (int i = 0; i < wordlistSize; i++) {
        char* word = wordlist[i];
        
        // Exact map
        addToMap(&exactMap, word, word);
        
        // Case map
        char lowerWord[MAX_LEN];
        strcpy(lowerWord, word);
        for (int j = 0; lowerWord[j]; j++) {
            lowerWord[j] = tolower(lowerWord[j]);
        }
        addToMap(&caseMap, lowerWord, word);
        
        // Vowel map
        char vowelPattern[MAX_LEN];
        normalizeVowels(word, vowelPattern);
        addToMap(&vowelMap, vowelPattern, word);
    }
    
    char** result = (char**)malloc(queriesSize * sizeof(char*));
    *returnSize = queriesSize;
    
    for (int i = 0; i < queriesSize; i++) {
        char* query = queries[i];
        char* match = NULL;
        
        // Priority 1: Exact match
        match = findInMap(&exactMap, query);
        if (match) {
            result[i] = strdup(match);
            continue;
        }
        
        // Priority 2: Case match
        char queryLower[MAX_LEN];
        strcpy(queryLower, query);
        for (int j = 0; queryLower[j]; j++) {
            queryLower[j] = tolower(queryLower[j]);
        }
        match = findInMap(&caseMap, queryLower);
        if (match) {
            result[i] = strdup(match);
            continue;
        }
        
        // Priority 3: Vowel match
        char queryPattern[MAX_LEN];
        normalizeVowels(query, queryPattern);
        match = findInMap(&vowelMap, queryPattern);
        if (match) {
            result[i] = strdup(match);
        } else {
            result[i] = strdup("");
        }
    }
    
    return result;
}

int main() {
    // Simplified main for demonstration
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(m × k + n × k)

Preprocess m words of length k, then process n queries of length k

✓ Linear Growth

Space Complexity

O(m × k)

Three hash maps storing patterns for m words

✓ Linear Space

31.3K Views

Medium Frequency

~25 min Avg. Time

847 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Hash Map Optimization — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler