We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Vowel Spellchecker

Number: 1006

Difficulty: Medium

Paid? No

Companies: Grammarly, Thumbtack

Problem Description

Given a wordlist and a set of queries, implement a spellchecker that corrects a query word by considering three levels of matching:

  1. Exact match (case-sensitive).
  2. Case-insensitive match.
  3. Match after replacing all vowels (a, e, i, o, u) in the query with a placeholder (treating any vowel as equivalent). Return the first word from the wordlist that matches the query based on the highest-precedence rule. If no match exists, return an empty string.

Key Insights

  • Use hash tables to efficiently check for exact, case-insensitive, and vowel-error matches.
  • For case-insensitive matching, store mapping of lowercase version of each word to the original word (only storing the first occurrence).
  • For vowel error matching, transform each word by replacing all vowels with a common character (e.g., '#') and map the transformed word to the original word (again, only the first occurrence).
  • First check for an exact match. If not, check the case-insensitive dictionary. Then, check the vowel-error dictionary.
  • Use helper functions to convert words to their vowel-normalized form.

Space and Time Complexity

Time Complexity: O(N * L + Q * L) where N is the number of words in the wordlist, Q is the number of queries, and L is the maximum length of words. This is because we process each word letter by letter. Space Complexity: O(N * L) due to auxiliary dictionaries storing modified forms of all words.

Solution

We build three dictionaries:

  1. An exact set of words to enable O(1) checks for matches.
  2. A case-insensitive dictionary mapping the lowercase word to the first occurrence in the wordlist.
  3. A vowel-error dictionary mapping a transformed word (where vowels are replaced with a placeholder, such as '#') to the first word from the wordlist.

For each query, we:

  1. Check if the query exists exactly in the wordlist.
  2. Check if the lowercase form of the query exists in the case-insensitive dictionary.
  3. Check if the transformed query (using the same vowel removal pattern) exists in the vowel-error dictionary. If none of the above yield a match, return an empty string.

Code Solutions

# Python code for Vowel Spellchecker

def devowel(word):
    # Replace vowels in the word with a placeholder '#'
    vowels = set("aeiou")
    return ''.join('#' if c in vowels else c for c in word.lower())

class Spellchecker:
    def spellchecker(self, wordlist, queries):
        # Exact match set
        exact_words = set(wordlist)
        
        # Case-insensitive dictionary: maps lower-case word to original word (first occurrence)
        case_insensitive = {}
        # Vowel error dictionary: maps devoweled word to original word (first occurrence)
        vowel_error = {}
        
        for word in wordlist:
            lower_word = word.lower()
            # Only set if not already present to preserve first occurrence
            if lower_word not in case_insensitive:
                case_insensitive[lower_word] = word
            devoweled = devowel(word)
            if devoweled not in vowel_error:
                vowel_error[devoweled] = word
        
        result = []
        for query in queries:
            # Check exact match
            if query in exact_words:
                result.append(query)
            # Check case-insensitive match
            elif query.lower() in case_insensitive:
                result.append(case_insensitive[query.lower()])
            # Check vowel error match
            elif devowel(query) in vowel_error:
                result.append(vowel_error[devowel(query)])
            else:
                result.append("")
        return result

# Example usage:
# wordlist = ["KiTe","kite","hare","Hare"]
# queries = ["kite","Kite","KiTe","Hare","HARE","Hear","hear","keti","keet","keto"]
# solver = Spellchecker()
# print(solver.spellchecker(wordlist, queries))
← Back to All Questions