Problem Description

You need to implement a spellchecker that takes a list of correct words (wordlist) and converts query words into their correct forms based on specific rules.

The spellchecker handles two types of spelling mistakes:

1. Capitalization Errors: If a query word matches a word in the wordlist when compared case-insensitively, return the matching word from the wordlist with its original casing.

• Example: wordlist = ["yellow"], query = "YellOw" → return "yellow"
• Example: wordlist = ["Yellow"], query = "yellow" → return "Yellow"

2. Vowel Errors: If a query word matches a word in the wordlist after replacing any vowels ('a', 'e', 'i', 'o', 'u') with any other vowel (case-insensitive comparison), return the matching word from the wordlist.

• Example: wordlist = ["YellOw"], query = "yollow" → return "YellOw" (the 'e' in yellow can be replaced with 'o')
• Example: wordlist = ["YellOw"], query = "yeellow" → return "" (no match - double vowels don't match single vowel)
• Example: wordlist = ["YellOw"], query = "yllw" → return "" (no match - missing vowel positions)

Priority Rules: The spellchecker follows this precedence order:

1. Exact match (case-sensitive): If the query exactly matches a word in the wordlist, return that exact word
2. Case-insensitive match: If the query matches a word ignoring case, return the first such match from the wordlist
3. Vowel error match: If the query matches a word after vowel substitution (case-insensitive), return the first such match from the wordlist
4. No match: If none of the above apply, return an empty string ""

Given an array of queries, return an array where each element is the corrected word for the corresponding query according to the rules above.

Intuition

The key insight is that we need to handle three different matching scenarios with specific priorities. Since we need to check multiple queries efficiently, preprocessing the wordlist into different representations will allow us to perform fast lookups.

Think about what we need to check for each query:

1. First, we need to check if the exact word exists (case-sensitive)
2. Then, we need to check if a case-insensitive version exists
3. Finally, we need to check if a vowel-variant exists

For efficient lookups, we can use hash tables. But how do we handle the different matching rules?

For exact matches, we can simply use a set to store all words from the wordlist and check membership in O(1) time.

For case-insensitive matches, we can normalize all words to lowercase and store them in a hash table. The key would be the lowercase version, and the value would be the original word from the wordlist. Since we need the "first such match", we use setdefault() to only store the first occurrence.

For vowel error matches, we need a way to identify words that differ only in vowels. The clever approach is to create a pattern where all vowels are replaced with a wildcard character (like *). For example, both "hello" and "hallo" would map to the pattern "h*ll*". This way, words that differ only in vowels will have the same pattern. We store these patterns in another hash table, again keeping only the first occurrence.

By preprocessing the wordlist into these three data structures (set for exact matches, low dictionary for case-insensitive matches, and pat dictionary for vowel patterns), we can process each query by checking these structures in order of priority: exact match → case match → vowel pattern match → no match (empty string).

This approach transforms what could be an O(n) search through the wordlist for each query into O(1) lookups, making the overall solution very efficient.

Solution Approach

The implementation uses three hash tables to handle the different matching scenarios efficiently:

1. Setting up the data structures:

• s = set(wordlist): A set to store all words for O(1) exact match lookups
• low = {}: A dictionary mapping lowercase words to their original forms in the wordlist
• pat = {}: A dictionary mapping vowel patterns to their original forms in the wordlist

2. Helper function for vowel pattern generation: The function f(w) creates a pattern by replacing all vowels with *:

def f(w):
    t = []
    for c in w:
        t.append("*" if c in "aeiou" else c)
    return "".join(t)

For example: f("hello") returns "h*ll*" and f("hallo") also returns "h*ll*".

3. Preprocessing the wordlist: We iterate through the wordlist once to populate our hash tables:

for w in wordlist:
    t = w.lower()
    low.setdefault(t, w)  # Store first occurrence for case-insensitive match
    pat.setdefault(f(t), w)  # Store first occurrence for vowel pattern match

The setdefault() method is crucial here - it only sets the value if the key doesn't exist, ensuring we keep the first occurrence as required by the problem.

4. Processing queries: For each query q, we check in order of priority:

for q in queries:
    if q in s:  # Priority 1: Exact match
        ans.append(q)
        continue
  
    q = q.lower()
    if q in low:  # Priority 2: Case-insensitive match
        ans.append(low[q])
        continue
  
    q = f(q)  # Convert to vowel pattern
    if q in pat:  # Priority 3: Vowel error match
        ans.append(pat[q])
        continue
  
    ans.append("")  # Priority 4: No match

Time Complexity:

• Preprocessing: O(n × m) where n is the number of words in wordlist and m is the average word length
• Query processing: O(k × m) where k is the number of queries
• Overall: O((n + k) × m)

Space Complexity: O(n × m) for storing the three hash tables

The solution elegantly handles all matching rules by preprocessing the wordlist into different representations and checking them in the specified priority order, ensuring both correctness and efficiency.

Example Walkthrough

Let's walk through a concrete example to understand how the solution works.

Given:

• wordlist = ["Yellow", "hello", "hEllo"]
• queries = ["yollow", "HELLO", "yallow", "help"]

Step 1: Preprocessing the wordlist

We create three data structures:

1. Exact match set: s = {"Yellow", "hello", "hEllo"}

2. Case-insensitive dictionary (low):

   • "Yellow" → lowercase is "yellow" → low["yellow"] = "Yellow"
   • "hello" → lowercase is "hello" → low["hello"] = "hello"
   • "hEllo" → lowercase is "hello" → already exists, skip (keep first occurrence)
   • Result: low = {"yellow": "Yellow", "hello": "hello"}

3. Vowel pattern dictionary (pat):

   • "Yellow" → lowercase "yellow" → pattern "yllw" → pat["y*ll*w"] = "Yellow"
   • "hello" → lowercase "hello" → pattern "hll" → pat["h*ll*"] = "hello"
   • "hEllo" → lowercase "hello" → pattern "hll" → already exists, skip
   • Result: pat = {"y*ll*w": "Yellow", "h*ll*": "hello"}

Step 2: Processing queries

Query 1: "yollow"

• Check exact match: "yollow" in s? No
• Convert to lowercase: "yollow"
• Check case match: "yollow" in low? No
• Convert to pattern: "yllw"
• Check pattern match: "yllw" in pat? Yes! → Return "Yellow"

Query 2: "HELLO"

• Check exact match: "HELLO" in s? No
• Convert to lowercase: "hello"
• Check case match: "hello" in low? Yes! → Return "hello"

Query 3: "yallow"

• Check exact match: "yallow" in s? No
• Convert to lowercase: "yallow"
• Check case match: "yallow" in low? No
• Convert to pattern: "yllw"
• Check pattern match: "yllw" in pat? Yes! → Return "Yellow"

Query 4: "help"

• Check exact match: "help" in s? No
• Convert to lowercase: "help"
• Check case match: "help" in low? No
• Convert to pattern: "h*lp"
• Check pattern match: "h*lp" in pat? No → Return ""

Final Result: ["Yellow", "hello", "Yellow", ""]

This example demonstrates how:

• The solution checks matches in priority order (exact → case → vowel)
• The preprocessing ensures we always return the first occurrence from wordlist
• Vowel patterns allow matching words with different vowels in the same positions
• Non-matching queries return empty strings

Solution Implementation

Time and Space Complexity

Time Complexity: O(n × L + m × L) where n is the length of wordlist, m is the length of queries, and L is the average length of words.

• Building the set s from wordlist: O(n × L) (hashing each word)
• Processing each word in wordlist to build low and pat dictionaries: O(n × L)
  • Converting to lowercase: O(L) per word
  • Creating pattern with f() function: O(L) per word
• Processing each query: O(m × L)
  • Set lookup: O(L) for hashing
  • Converting to lowercase: O(L)
  • Creating pattern with f(): O(L)
  • Dictionary lookups: O(L) for hashing

Since L is typically considered constant or small compared to n and m, this simplifies to O(n + m).

Space Complexity: O(n × L) which simplifies to O(n) when L is considered constant.

• Set s stores all words from wordlist: O(n × L)
• Dictionary low stores at most n lowercase mappings: O(n × L)
• Dictionary pat stores at most n pattern mappings: O(n × L)
• List ans stores m results: O(m × L)

The dominant space usage comes from storing the wordlist-related data structures, giving us O(n) when word length is considered constant.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Not Preserving the First Occurrence for Duplicate Patterns

One of the most common mistakes is overwriting dictionary values when multiple words in the wordlist map to the same lowercase form or vowel pattern. The problem specifically requires returning the first matching word from the wordlist.

Incorrect Implementation:

# WRONG: This overwrites previous values
for word in wordlist:
    word_lower = word.lower()
    lowercase_dict[word_lower] = word  # Overwrites if key exists!
    pattern = devowel(word_lower)
    vowel_pattern_dict[pattern] = word  # Overwrites if key exists!

Example where this fails:

• wordlist = ["Yellow", "yellow"], query = "yeLLow"
• Incorrect code would return "yellow" (last occurrence)
• Correct answer should be "Yellow" (first occurrence)

Solution: Always check if the key exists before setting it, or use setdefault():

# Method 1: Check before setting
if word_lower not in lowercase_dict:
    lowercase_dict[word_lower] = word

# Method 2: Use setdefault
lowercase_dict.setdefault(word_lower, word)

2. Case Sensitivity Issues in Vowel Detection

Another common mistake is forgetting to handle uppercase vowels when creating the vowel pattern.

Incorrect Implementation:

def devowel(word: str) -> str:
    pattern = []
    for char in word:
        if char in "aeiou":  # WRONG: Only checks lowercase vowels!
            pattern.append("*")
        else:
            pattern.append(char)
    return "".join(pattern)

Example where this fails:

• wordlist = ["KiTe"], query = "kati"
• The pattern for "KiTe" would incorrectly be "KT" instead of "kt"
• This would cause a mismatch even though it should match

Solution: Always convert to lowercase before processing the vowel pattern:

# Process the lowercase version for pattern matching
word_lower = word.lower()
pattern = devowel(word_lower)  # Pass lowercase version

3. Incorrect Priority Order

Some implementations check all conditions and then decide, rather than following the strict priority order with early returns.

Incorrect Implementation:

# WRONG: Checks all conditions then decides
for query in queries:
    exact_match = query if query in word_set else None
    case_match = lowercase_dict.get(query.lower(), None)
    vowel_match = vowel_pattern_dict.get(devowel(query.lower()), None)
  
    # This doesn't guarantee priority order!
    result.append(exact_match or case_match or vowel_match or "")

Solution: Use continue statements to ensure each priority level is handled before moving to the next:

for query in queries:
    if query in word_set:
        result.append(query)
        continue  # Stop here if exact match found
  
    query_lower = query.lower()
    if query_lower in lowercase_dict:
        result.append(lowercase_dict[query_lower])
        continue  # Stop here if case-insensitive match found
  
    # Only check vowel pattern if no higher priority match
    query_pattern = devowel(query_lower)
    if query_pattern in vowel_pattern_dict:
        result.append(vowel_pattern_dict[query_pattern])
        continue
  
    result.append("")

4. Modifying the Original Query Variable

A subtle bug can occur when reusing the query variable name:

Incorrect Implementation:

for query in queries:
    if query in word_set:
        result.append(query)
        continue
  
    query = query.lower()  # DANGER: Overwrites original query!
    if query in lowercase_dict:
        result.append(lowercase_dict[query])
        continue
  
    query = devowel(query)  # Now query is a pattern, not the original!
    # ...

Solution: Use different variable names to preserve the original query:

for query in queries:
    if query in word_set:
        result.append(query)
        continue
  
    query_lower = query.lower()  # Use different variable name
    if query_lower in lowercase_dict:
        result.append(lowercase_dict[query_lower])
        continue
  
    query_pattern = devowel(query_lower)  # Use different variable name
    # ...