Vowel Spellchecker

Problem Statement

The task involves creating a spellchecker that can correct user queries based on a given list of correctly spelled words, referred to as wordlist. The spellchecker should handle two primary types of common spelling errors:

• Capitalization Errors: This type of error occurs when the query matches a word in the wordlist regardless of the case (i.e., irrespective of whether it is uppercase or lowercase). The spellchecker should correct the query to match the exact case of the word as it appears in the wordlist.
• Vowel Errors: This error type involves queries where vowels may be miswritten. The spellchecker should be able to recognize the word even if any of its vowels are incorrectly used, and it should return the word maintaining the case found in the wordlist.

The correction system follows a hierarchy of rules for deciding the correct form of a queried word:

1. If a query matches a word in the wordlist exactly, including the same case, it is considered correctly spelled.
2. If there is no case-sensitive match, the query is corrected to the first case-insensitive match found in the wordlist.
3. If no direct match is found, the spellchecker attempts to match the word by adjusting only the vowels.
4. If there are still no matches after checking for vowel errors, the query is left uncorrected (returned as an empty string).

The objective is to process an array of queries and return the corrected form of each query based on the rules and corrections as described above.

Examples

Example 1

Input:

wordlist = ["KiTe","kite","hare","Hare"], queries = ["kite","Kite","KiTe","Hare","HARE","Hear","hear","keti","keet","keto"]

Output:

["kite","KiTe","KiTe","Hare","hare","","","KiTe","","KiTe"]

Example 2

Input:

wordlist = ["yellow"], queries = ["YellOw"]

Output:

["yellow"]

Constraints

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

Approach and Intuition

We approach this spellchecking task by leveraging the properties of sets and dictionaries in programming due to their efficient lookup times. Here’s a step-by-step breakdown of the method to implement the spellchecker:

1. Store Words in Various Forms:

   • Create a set to store all the words exactly as they appear in the wordlist for case-sensitive matches.
   • Use a dictionary to store the first occurrence of each word in a case-insensitive manner. This helps in quickly referencing the correct casing of the word based on a case-insensitive match.
   • Create another dictionary to handle the vowel error correction, where the keys are words from the wordlist with all vowels replaced by a placeholder character (like '*') and the values are the properly cased words from the wordlist.

2. Process Each Query:

   • Check if the query matches any word in the case-sensitive set. If it does, return that word directly.
   • If no case-sensitive match is found, convert the query to lowercase and check against the case-insensitive dictionary. If a match is found, replace the query with this match.
   • If neither of the above checks yields a result, replace all vowels in the query with a placeholder and check this modified query against the vowel-error dictionary.
   • If there are still no matches, return an empty string for that query as a fallback.

3. Output Results:

   • For each query, output the correct form based on the hierarchal rules defined. Collect these results in an array corresponding to the processed queries.

This method ensures that the spellchecking is done efficiently, handling up to the maximum constraints provided. The use of dictionaries and sets facilitates quick retrievals, keeping the operations within feasible time limits even for the higher bounds of the input sizes.

Solutions

class SpellChecker {
    Set<String> exactMatches;
    Map<String, String> lowercaseMap;
    Map<String, String> vowellessMap;
    
    public String[] checkSpelling(String[] wordlist, String[] queries) {
        exactMatches = new HashSet();
        lowercaseMap = new HashMap();
        vowellessMap = new HashMap();
    
        for (String word: wordlist) {
            exactMatches.add(word);
    
            String wordLower = word.toLowerCase();
            lowercaseMap.putIfAbsent(wordLower, word);
    
            String devoweledWord = removeVowels(wordLower);
            vowellessMap.putIfAbsent(devoweledWord, word);
        }
    
        String[] result = new String[queries.length];
        int index = 0;
        for (String query: queries)
            result[index++] = findMatch(query);
        return result;
    }
    
    public String findMatch(String query) {
        if (exactMatches.contains(query))
            return query;
    
        String queryLower = query.toLowerCase();
        if (lowercaseMap.containsKey(queryLower))
            return lowercaseMap.get(queryLower);
    
        String queryDevoweled = removeVowels(queryLower);
        if (vowellessMap.containsKey(queryDevoweled))
            return vowellessMap.get(queryDevoweled);
    
        return "";
    }
    
    public String removeVowels(String word) {
        StringBuilder result = new StringBuilder();
        for (char c : word.toCharArray())
            result.append(isVowelChar(c) ? '*' : c);
        return result.toString();
    }
    
    public boolean isVowelChar(char c) {
        return "aeiou".indexOf(c) != -1;
    }
}