What is the time complexity of Vowel Spellchecker?

The optimal solution has a time complexity of O(m*n).

What data structures are used to solve Vowel Spellchecker?

This problem uses Array, Hash Table, String. Understanding these concepts is essential for solving this Medium problem efficiently.

What are the key insights for solving Vowel Spellchecker?

Insight 1: Using hash tables (or sets/maps in various languages) is crucial for efficient lookup of words in the wordlist, significantly reducing the time complexity of the spellchecking process. Insight 2: Preprocessing the wordlist by creating separate data structures for exact matches, case-insensitive matches, and vowel error matches allows for a structured approach to the spellchecking process, making it easier to follow the precedence rules.

Which companies ask LeetCode 966. Vowel Spellchecker in interviews?

This problem is frequently asked at Grammarly.

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

Vowel Spellchecker - LeetCode 966 Solution

Vowel Spellchecker - Complete Solution Guide

Vowel Spellchecker is LeetCode problem 966, a Medium level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

Problem Statement

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" Exampl

Detailed Explanation

The problem requires implementing a spellchecker that corrects spelling mistakes in given queries against a provided wordlist. The spellchecker must handle two types of errors: capitalization errors (where the query matches a word in the wordlist case-insensitively) and vowel errors (where replacing vowels in the query with any vowel matches a word in the wordlist case-insensitively). The spellchecker follows a specific precedence: exact match (case-sensitive), capitalization match (first occurrence), vowel error match (first occurrence), and returns an empty string if no match is found.

Solution Approach

The solution preprocesses the wordlist by creating three data structures: a set for exact matches, a map for case-insensitive matches, and a map for vowel error matches. The code then iterates through the queries and checks for matches in the order of precedence specified in the problem statement: exact match, case-insensitive match, and vowel error match. The first match found is returned. If no match is found, an empty string is returned.

Step-by-Step Algorithm

Step 1: Create a set `exact_match` to store the words from the `wordlist` for exact matching (case-sensitive).
Step 2: Create a map `case_insensitive_match` to store the lowercase versions of words from `wordlist` as keys and their original case versions as values. The first occurrence of each lowercase word is stored.
Step 3: Create a map `vowel_error_match` to store 'devoweled' versions of lowercase words from `wordlist` as keys and their original case versions as values. The first occurrence of each 'devoweled' word is stored. 'Devoweled' means that all vowels ('a', 'e', 'i', 'o', 'u') are replaced by '*' .
Step 4: Iterate through the `queries` array.
Step 5: For each `query`, check if it exists in the `exact_match` set. If it does, return the `query` itself.
Step 6: If no exact match is found, convert the `query` to lowercase and check if it exists as a key in the `case_insensitive_match` map. If it does, return the value associated with that key (the original case word from `wordlist`).
Step 7: If no case-insensitive match is found, create a 'devoweled' version of the lowercase `query` (replace vowels with '*'). Check if this 'devoweled' version exists as a key in the `vowel_error_match` map. If it does, return the value associated with that key (the original case word from `wordlist`).
Step 8: If none of the above matches are found, return an empty string.

Key Insights

Insight 1: Using hash tables (or sets/maps in various languages) is crucial for efficient lookup of words in the wordlist, significantly reducing the time complexity of the spellchecking process.
Insight 2: Preprocessing the wordlist by creating separate data structures for exact matches, case-insensitive matches, and vowel error matches allows for a structured approach to the spellchecking process, making it easier to follow the precedence rules.
Insight 3: The choice of using '*' to represent vowels in the devoweled words simplifies the vowel error matching process, as it effectively groups all vowel variations into a single representation.

Complexity Analysis

Time Complexity: O(m*n)

Space Complexity: O(n)

Topics

This problem involves: Array, Hash Table, String.

Companies

Asked at: Grammarly.

Vowel Spellchecker | LeetCode 966

Medium

Array Hash Table String

Time: O(m*n)Space: O(n)

Solution Code

Available in:

import java.util.*;

class Solution {
    public String[] spellchecker(String[] wordlist, String[] queries) {
        Set<String> exact_match = new HashSet<>(Arrays.asList(wordlist));
        Map<String, String> case_insensitive_match = new HashMap<>();
        Map<String, String> vowel_error_match = new HashMap<>();

        for (String word : wordlist) {
            String lower_word = word.toLowerCase();
            if (!case_insensitive_match.containsKey(lower_word)) {
                case_insensitive_match.put(lower_word, word);
            }

            StringBuilder devoweled_word_builder = new StringBuilder();
            for (char c : lower_word.toCharArray()) {
                if ("aeiou".indexOf(c) != -1) {
                    devoweled_word_builder.append('*');
                } else {
                    devoweled_word_builder.append(c);
                }
            }
            String devoweled_word = devoweled_word_builder.toString();

            if (!vowel_error_match.containsKey(devoweled_word)) {
                vowel_error_match.put(devoweled_word, word);
            }
        }

        String[] result = new String[queries.length];
        for (int i = 0; i < queries.length; i++) {
            String query = queries[i];
            if (exact_match.contains(query)) {
                result[i] = query;
                continue;
            }

            String lower_query = query.toLowerCase();
            if (case_insensitive_match.containsKey(lower_query)) {
                result[i] = case_insensitive_match.get(lower_query);
                continue;
            }

            StringBuilder devoweled_query_builder = new StringBuilder();
            for (char c : lower_query.toCharArray()) {
                if ("aeiou".indexOf(c) != -1) {
                    devoweled_query_builder.append('*');
                } else {
                    devoweled_query_builder.append(c);
                }
            }
            String devoweled_query = devoweled_query_builder.toString();
            if (vowel_error_match.containsKey(devoweled_query)) {
                result[i] = vowel_error_match.get(devoweled_query);
                continue;
            }

            result[i] = "";
        }

        return result;
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 966: Vowel Spellchecker - Detailed explanation and solution approaches.

Topics

Array Hash Table String

Companies

Grammarly

Stats

Difficulty:Medium

Languages:4

Companies:1

Problem #:966

Problem Explanation

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

8 steps

1
Step 1: Create a set `exact_match` to store the words from the `wordlist` for exact matching (case-sensitive).
2
Step 2: Create a map `case_insensitive_match` to store the lowercase versions of words from `wordlist` as keys and their original case versions as values. The first occurrence of each lowercase word is stored.
3
Step 3: Create a map `vowel_error_match` to store 'devoweled' versions of lowercase words from `wordlist` as keys and their original case versions as values. The first occurrence of each 'devoweled' word is stored. 'Devoweled' means that all vowels ('a', 'e', 'i', 'o', 'u') are replaced by '*' .
4
Step 4: Iterate through the `queries` array.
5
Step 5: For each `query`, check if it exists in the `exact_match` set. If it does, return the `query` itself.
6
Step 6: If no exact match is found, convert the `query` to lowercase and check if it exists as a key in the `case_insensitive_match` map. If it does, return the value associated with that key (the original case word from `wordlist`).
7
Step 7: If no case-insensitive match is found, create a 'devoweled' version of the lowercase `query` (replace vowels with '*'). Check if this 'devoweled' version exists as a key in the `vowel_error_match` map. If it does, return the value associated with that key (the original case word from `wordlist`).
8
Step 8: If none of the above matches are found, return an empty string.

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(m*n)

💾

Space Complexity

O(n)

📦 Linear space - Memory grows with input size.

📝

Why?

The time complexity is dominated by the preprocessing steps (creating the maps) and iterating through the queries. The space complexity is dominated by the storage required for the maps, which depend on the number and length of words in the wordlist. In the C code the hash table has a higher space complexity because the HashTable structure itself is allocated and needs to be kept track of.

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

Trie-based approach

A trie data structure can be used to store the wordlist. By modifying the search algorithm in the trie, we can implement case-insensitive and vowel-error matching.

Time: O(M * L) in the worst case, but can be faster on average due to trie pruningSpace: O(N * L), where N is the number of words and L is the average word length.

Trade-offs: Trie-based approaches can be more memory-efficient than hash tables in certain scenarios, especially if there are many common prefixes in the wordlist. However, the implementation can be more complex, and the constant factors might be higher, leading to slower performance for smaller inputs.

✨

Key Insights

1Insight 1: Using hash tables (or sets/maps in various languages) is crucial for efficient lookup of words in the wordlist, significantly reducing the time complexity of the spellchecking process.
2Insight 2: Preprocessing the wordlist by creating separate data structures for exact matches, case-insensitive matches, and vowel error matches allows for a structured approach to the spellchecking process, making it easier to follow the precedence rules.
3Insight 3: The choice of using '*' to represent vowels in the devoweled words simplifies the vowel error matching process, as it effectively groups all vowel variations into a single representation.

📚

Key Terms Explained

For Students

Array

A collection of items stored at contiguous memory locations. Like a row of boxes.

Hash Table

A data structure that maps keys to values for quick lookup. Like a dictionary!

String

A sequence of characters. Like a word or sentence in programming!

Edge Cases

Edge case 1: Empty wordlist. The algorithm correctly handles this because the maps will be empty, resulting in empty strings being returned for all queries.
Edge case 2: Queries with no matching words in the wordlist. The algorithm correctly returns empty strings for such queries.
Edge case 3: Wordlist containing duplicate words with different capitalization. The algorithm prioritizes the first occurrence of each lowercase word when populating the `case_insensitive_match` map, as required by the problem statement.
Edge case 4: Vowel errors that could match multiple words in the wordlist. The algorithm prioritizes the first word encountered in the wordlist during the construction of the `vowel_error_match` map.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Not handling the precedence rules correctly. The algorithm must check for exact matches first, then case-insensitive matches, and finally vowel error matches. Failing to follow this order will result in incorrect spell corrections.

✗Common mistake 2: Not considering the first occurrence rule for case-insensitive and vowel error matches. The algorithm must store only the first matching word from the wordlist when constructing the maps for these types of matches. Overwriting the first match with a later match will lead to incorrect behavior.

✗Common mistake 3: Inefficiently searching for vowels. Instead of checking each character against all vowels individually, a set of vowels can be precomputed for faster lookups.

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Real-world scenario 1: Implementing spellcheckers in text editors, word processors, and search engines. The vowel and capitalization error correction mechanisms are commonly used to suggest corrections for misspelled words.

🏦Real-world scenario 2: Suggesting corrections for user input in voice assistants. Since voice recognition can be error-prone, spellcheckers can help improve the accuracy of commands and queries.

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

When dealing with arrays, always consider if sorting would simplify the problem. Many array problems have O(n) solutions using hash maps or two-pointer technique.

🎯 Interview Tip

Medium problems are the bread and butter of technical interviews. Practice explaining your approach before coding.

⚠️ Watch Out

Off-by-one errors are the most common mistake. Double-check your loop bounds and array indices.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: August 6, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

The key insight here is recognizing the pattern. Once you see it, the solution becomes straightforward.

@AlgoMasterJul 14

I was asked this exact problem at my Google interview. The interviewer wanted me to optimize space complexity.

@InterviewProJul 7

❓

Frequently Asked Questions

What is the most efficient way to solve array problems?

Most array problems can be solved efficiently using techniques like two-pointer approach, sliding window, or hash maps. The key is identifying whether the array is sorted (enabling binary search) or if tracking seen elements (using hash maps) can help achieve O(n) time complexity.

What are the trade-offs of using a hash table?

Hash tables provide O(1) average-case lookup, insertion, and deletion, making them ideal for frequency counting and duplicate detection. However, they use O(n) extra space and may degrade to O(n) time in worst-case scenarios with hash collisions. Always consider if the space trade-off is acceptable.

What techniques are commonly tested in medium-difficulty problems?

Medium problems often require combining multiple techniques: two-pointer with hash maps, BFS/DFS with state tracking, dynamic programming with optimization, or divide-and-conquer approaches. They test your ability to recognize patterns and choose the right combination of techniques.

How should I practice algorithm problems effectively?

Focus on understanding patterns rather than memorizing solutions. After solving a problem, review optimal solutions and understand the intuition. Group similar problems to recognize patterns. Practice explaining your approach out loud. Review problems after a few days to test retention.

What is the optimal approach for "Vowel Spellchecker"?

For this medium-level Array problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether hash table techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?