966. Vowel Spellchecker LeetCode Solution

In this guide, you will get 966. Vowel Spellchecker LeetCode Solution with the best time and space complexity. The solution to Vowel Spellchecker problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Vowel Spellchecker solution in C++
Vowel Spellchecker solution in Java
Vowel Spellchecker solution in Python
Additional Resources

966. Vowel Spellchecker LeetCode Solution image

Problem Statement of Vowel Spellchecker

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”
Example: wordlist = [“yellow”], query = “yellow”: correct = “yellow”

Vowel Errors: If after replacing the vowels (‘a’, ‘e’, ‘i’, ‘o’, ‘u’) of the query word with any vowel individually, it matches a word in the wordlist (case-insensitive), then the query word is returned with the same case as the match in the wordlist.

Example: wordlist = [“YellOw”], query = “yollow”: correct = “YellOw”
Example: wordlist = [“YellOw”], query = “yeellow”: correct = “” (no match)
Example: wordlist = [“YellOw”], query = “yllw”: correct = “” (no match)

In addition, the spell checker operates under the following precedence rules:

When the query exactly matches a word in the wordlist (case-sensitive), you should return the same word back.
When the query matches a word up to capitlization, you should return the first such match in the wordlist.
When the query matches a word up to vowel errors, you should return the first such match in the wordlist.
If the query has no matches in the wordlist, you should return the empty string.

Given some queries, return a list of words answer, where answer[i] is the correct word for query = queries[i].

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.

Complexity Analysis

Time Complexity:
Space Complexity:

966. Vowel Spellchecker LeetCode Solution in C++

class Solution {
 public:
  vector<string> spellchecker(vector<string>& wordlist,
                              vector<string>& queries) {
    vector<string> ans;
    unordered_map<string, string> dict;

    for (const string& word : wordlist) {
      dict.insert({word, word});
      dict.insert({lowerKey(word), word});
      dict.insert({vowelKey(word), word});
    }

    for (const string& query : queries)
      if (const auto it = dict.find(query); it != dict.cend())
        ans.push_back(it->second);
      else if (const auto it = dict.find(lowerKey(query)); it != dict.cend())
        ans.push_back(it->second);
      else if (const auto it = dict.find(vowelKey(query)); it != dict.cend())
        ans.push_back(it->second);
      else
        ans.push_back("");

    return ans;
  }

 private:
  string lowerKey(const string& word) {
    string s{"$"};
    for (const char c : word)
      s += tolower(c);
    return s;
  }

  string vowelKey(const string& word) {
    string s;
    for (const char c : word)
      s += isVowel(c) ? '*' : tolower(c);
    return s;
  }

  bool isVowel(char c) {
    static constexpr string_view kVowels = "aeiouAEIOU";
    return kVowels.find(c) != string_view::npos;
  }
};
/* code provided by PROGIEZ */

966. Vowel Spellchecker LeetCode Solution in Java

class Solution {
  public String[] spellchecker(String[] wordlist, String[] queries) {
    List<String> ans = new ArrayList<>();
    Map<String, String> dict = new HashMap<>();

    for (final String word : wordlist) {
      dict.putIfAbsent(word, word);
      dict.putIfAbsent(lowerKey(word), word);
      dict.putIfAbsent(vowelKey(word), word);
    }

    for (final String query : queries)
      if (dict.containsKey(query))
        ans.add(dict.get(query));
      else if (dict.containsKey(lowerKey(query)))
        ans.add(dict.get(lowerKey(query)));
      else if (dict.containsKey(vowelKey(query)))
        ans.add(dict.get(vowelKey(query)));
      else
        ans.add("");

    return ans.toArray(new String[0]);
  }

  private String lowerKey(final String word) {
    return "$" + word.toLowerCase();
  }

  private String vowelKey(final String word) {
    StringBuilder sb = new StringBuilder();
    for (final char c : word.toCharArray())
      sb.append(isVowel(c) ? '*' : Character.toLowerCase(c));
    return sb.toString();
  }

  private boolean isVowel(char c) {
    return "aeiouAEIOU".indexOf(c) != -1;
  }
}
// code provided by PROGIEZ

966. Vowel Spellchecker LeetCode Solution in Python

class Solution:
  def spellchecker(self, wordlist: list[str], queries: list[str]) -> list[str]:
    def lowerKey(word: str) -> str:
      return '$' + ''.join([c.lower() for c in word])

    def vowelKey(word: str) -> str:
      return ''.join(['*' if c.lower() in 'aeiou' else c.lower() for c in word])

    ans = []
    dict = {}

    for word in wordlist:
      dict.setdefault(word, word)
      dict.setdefault(lowerKey(word), word)
      dict.setdefault(vowelKey(word), word)

    for query in queries:
      if query in dict:
        ans.append(dict[query])
      elif lowerKey(query) in dict:
        ans.append(dict[lowerKey(query)])
      elif vowelKey(query) in dict:
        ans.append(dict[vowelKey(query)])
      else:
        ans.append('')

    return ans
 # code by PROGIEZ