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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Vowel Spellchecker

Difficulty: Medium

Problem Description

Given a wordlist, we want to implement a spellchecker that converts a query word into a correct word. The spell checker handles two categories of spelling mistakes: capitalization and vowel errors. The function should return the correct word based on a set of precedence rules when comparing the query against the wordlist.

Key Insights

  • The spell checker first checks for an exact case-sensitive match.
  • If no exact match is found, it checks for a case-insensitive match.
  • If that also fails, it checks for matches by replacing vowels in the query word.
  • The first match found according to the precedence rules should be returned, or an empty string if no matches exist.

Space and Time Complexity

Time Complexity: O(N * M), where N is the number of queries and M is the average length of the words in the wordlist. Space Complexity: O(W), where W is the number of unique words in the wordlist for storage in the hash table.

Solution

To solve the problem, we can use a hash table (dictionary) to store the words in the wordlist for quick lookups. We will create a normalized version of each word by replacing its vowels with a wildcard character. The algorithm follows these steps:

  1. Create a dictionary to map each word in the wordlist to its original form.
  2. Create another dictionary for words normalized by vowel replacement.
  3. For each query, check for an exact match in the dictionary.
  4. If not found, check for a case-insensitive match.
  5. Finally, check the vowel-normalized dictionary for matches.
  6. Return the appropriate match based on the precedence rules.

Code Solutions

def spellchecker(wordlist, queries):
    original_map = {}
    vowel_map = {}
    vowels = 'aeiou'
    
    # Populate the maps
    for word in wordlist:
        original_map[word] = word  # Store the original word
        normalized_word = ''.join(c if c not in vowels else '*' for c in word.lower())
        vowel_map[normalized_word] = word  # Store normalized form
    
    results = []
    
    for query in queries:
        # 1. Exact match
        if query in original_map:
            results.append(original_map[query])
            continue
        
        # 2. Case-insensitive match
        lower_query = query.lower()
        if lower_query in original_map:
            results.append(original_map[lower_query])
            continue
        
        # 3. Vowel error match
        normalized_query = ''.join(c if c not in vowels else '*' for c in lower_query)
        if normalized_query in vowel_map:
            results.append(vowel_map[normalized_query])
            continue
        
        # No match
        results.append('')
    
    return results
← Back to All Questions