# Vowel Spellchecker
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/vowel-spellchecker)
Canonical: https://scaleengineer.com/dsa/problems/vowel-spellchecker
**Data structures:** Array, Hash Table, String
**Companies:** [Grammarly](https://scaleengineer.com/companies/grammarly)
---
## Problem
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.

# Approaches
## Brute Force Iteration
This approach directly translates the problem's requirements into code without optimization. For each query, it scans the entire `wordlist` to find a match according to the specified precedence: exact match, case-insensitive match, and then vowel-error match. This leads to a very high time complexity as the `wordlist` is processed repeatedly.
**Time:** O(M * N * L), where M is the number of queries, N is the number of words in `wordlist`, and L is the average word length. For each of the M queries, we iterate through N words, and for each word, we perform operations (like `equalsIgnoreCase` or `devowel`) that take O(L) time. · **Space:** O(N*L), where N is the number of words in `wordlist` and L is the average word length. This space is used to store the `HashSet` for exact matches.
**Pros:** Simple to understand and implement as it directly follows the problem statement.; Uses minimal complex logic.
**Cons:** Highly inefficient due to nested loops, causing it to be very slow for larger inputs.; Likely to exceed the time limit on platforms like LeetCode for the given constraints.
### Explanation
The brute-force method tackles the problem by iterating through all possibilities for each query. We first handle the highest-priority case: an exact, case-sensitive match. To do this efficiently, we can put all words from the `wordlist` into a `HashSet` for O(1) average time lookups. If a query is found in this set, we have our answer.

If no exact match exists, we must then search for a case-insensitive match and a vowel-error match. We iterate through the entire `wordlist` from the beginning. During this scan, we keep track of the *first* case-insensitive match and the *first* vowel-error match we encounter. A helper function is used to create a "devoweled" form of a word (e.g., `"yellOw"` -> `"y*ll*w"`) for the vowel-error check. After scanning the whole list, we check if we found a case-insensitive match. If so, that's our answer. If not, we check if we found a vowel-error match. If neither type of match was found, the answer is an empty string. This entire process is repeated for every single query.

```java
class Solution {
    public String[] spellchecker(String[] wordlist, String[] queries) {
        Set<String> exactSet = new HashSet<>(Arrays.asList(wordlist));
        String[] result = new String[queries.length];

        for (int i = 0; i < queries.length; i++) {
            String query = queries[i];
            if (exactSet.contains(query)) {
                result[i] = query;
                continue;
            }

            String lowerQuery = query.toLowerCase();
            String devowelQuery = devowel(lowerQuery);
            
            String capMatch = "";
            String vowelMatch = "";

            for (String word : wordlist) {
                if (capMatch.isEmpty() && word.equalsIgnoreCase(query)) {
                    capMatch = word;
                }
                if (vowelMatch.isEmpty() && devowel(word.toLowerCase()).equals(devowelQuery)) {
                    vowelMatch = word;
                }
            }

            if (!capMatch.isEmpty()) {
                result[i] = capMatch;
            } else if (!vowelMatch.isEmpty()) {
                result[i] = vowelMatch;
            } else {
                result[i] = "";
            }
        }
        return result;
    }

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

    private boolean isVowel(char c) {
        return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
    }
}
```
### Algorithm
1. Create a `HashSet<String>` called `exactSet` containing all words from the `wordlist`. This allows for fast, case-sensitive lookups.
2. Initialize a `result` array to store the answers for each query.
3. Iterate through each `query` in the `queries` array:
    a. First, check for an exact match. If `exactSet.contains(query)`, set the corresponding result to `query` and continue to the next query.
    b. If no exact match is found, initialize two strings, `capMatch = ""` and `vowelMatch = ""`, to store the first potential matches for capitalization and vowel errors.
    c. Pre-calculate the lowercase and "devoweled" versions of the current query to avoid repeated computations inside the loop.
    d. Iterate through every `word` in the `wordlist`:
        i. If a capitalization match hasn't been found yet (`capMatch` is empty) and the current `word` matches the `query` case-insensitively, store this `word` in `capMatch`.
        ii. If a vowel error match hasn't been found yet (`vowelMatch` is empty) and the devoweled version of the current `word` matches the devoweled `query`, store this `word` in `vowelMatch`.
    e. After checking the entire `wordlist`, apply the precedence rules. If `capMatch` was found, it takes priority. Otherwise, use `vowelMatch`. If neither was found, the result is an empty string.
4. Return the `result` array.

## Pre-computation with Hash Maps
This optimal approach avoids re-computation by pre-processing the `wordlist`. It uses a `HashSet` for exact matches and two `HashMaps` to store mappings for case-insensitive and vowel-error matches. This allows each query to be resolved in near-constant time (proportional to query length) by looking up the transformed query in these data structures, dramatically improving performance.
**Time:** O(N*L + M*L), where N is the length of `wordlist`, M is the length of `queries`, and L is the average word length. The `O(N*L)` term comes from the one-time preprocessing of the `wordlist`. The `O(M*L)` term comes from processing each query, which involves lookups that take time proportional to the query length. · **Space:** O(N*L), where N is the number of words in `wordlist` and L is the average word length. This space is required to store the three data structures.
**Pros:** Extremely efficient time complexity, making it suitable for large inputs.; Processes the wordlist only once, avoiding redundant computations.
**Cons:** Requires additional space to store the pre-computed maps and set.
### Explanation
To optimize the spellchecking process, we can pre-process the `wordlist` and store the necessary information in efficient data structures. This avoids the costly O(N) scan for each query.

We use three structures:
1.  **`exactSet` (a `HashSet<String>`):** Stores all words from the `wordlist` for O(1) average time lookup of exact, case-sensitive matches.
2.  **`capMap` (a `HashMap<String, String>`):** Stores mappings from a lowercase word to the first original word from the `wordlist` that produces it. For example, if `wordlist` is `["KiTe", "kite"]`, the map will contain `{"kite": "KiTe"}`.
3.  **`vowelMap` (a `HashMap<String, String>`):** Stores mappings from a "devoweled" word (lowercase with vowels replaced, e.g., `k*t*`) to the first original word that produces it.

We populate these structures by iterating through the `wordlist` just once. The use of `putIfAbsent` (or checking if a key exists before putting) naturally handles the "return the first such match" rule.

Once the setup is complete, processing each query becomes very fast. We check our data structures in the correct order of precedence: first `exactSet`, then `capMap`, and finally `vowelMap`. The first match found determines the result. If no match is found after checking all three, the result is an empty string.

```java
class Solution {
    public String[] spellchecker(String[] wordlist, String[] queries) {
        Set<String> exactSet = new HashSet<>();
        Map<String, String> capMap = new HashMap<>();
        Map<String, String> vowelMap = new HashMap<>();

        for (String word : wordlist) {
            exactSet.add(word);
            
            String lowerWord = word.toLowerCase();
            capMap.putIfAbsent(lowerWord, word);
            
            String devowelWord = devowel(lowerWord);
            vowelMap.putIfAbsent(devowelWord, word);
        }

        String[] result = new String[queries.length];
        for (int i = 0; i < queries.length; i++) {
            String query = queries[i];
            if (exactSet.contains(query)) {
                result[i] = query;
                continue;
            }

            String lowerQuery = query.toLowerCase();
            if (capMap.containsKey(lowerQuery)) {
                result[i] = capMap.get(lowerQuery);
                continue;
            }

            String devowelQuery = devowel(lowerQuery);
            if (vowelMap.containsKey(devowelQuery)) {
                result[i] = vowelMap.get(devowelQuery);
                continue;
            }
            
            result[i] = "";
        }
        return result;
    }

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

    private boolean isVowel(char c) {
        return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
    }
}
```
### Algorithm
1. **Preprocessing:**
    a. Initialize three data structures: a `HashSet<String>` for exact matches (`exactSet`), a `HashMap<String, String>` for case-insensitive matches (`capMap`), and another `HashMap<String, String>` for vowel-error matches (`vowelMap`).
    b. Iterate through the `wordlist` once. For each `word`:
        i. Add the `word` to `exactSet`.
        ii. Convert the `word` to lowercase. Use this as a key and the original `word` as the value. Add this pair to `capMap` only if the key is not already present (to respect the "first match" rule).
        iii. Create a "devoweled" version of the lowercase word. Use this as a key and the original `word` as the value. Add this pair to `vowelMap` only if the key is not already present.
2. **Query Processing:**
    a. Initialize a `result` array.
    b. Iterate through each `query` in the `queries` array.
    c. Check for a match in order of precedence:
        i. If `exactSet` contains the `query`, this is the answer.
        ii. Else, check if `capMap` contains the lowercase `query` as a key. If yes, the corresponding value is the answer.
        iii. Else, check if `vowelMap` contains the devoweled, lowercase `query` as a key. If yes, the corresponding value is the answer.
        iv. If no match is found in any of the data structures, the answer is an empty string.
3. Return the `result` array.

# Solutions
### Java

```java
class Solution {
public
  String[] spellchecker(String[] wordlist, String[] queries) {
    Set<String> s = new HashSet<>();
    Map<String, String> low = new HashMap<>();
    Map<String, String> pat = new HashMap<>();
    for (String w : wordlist) {
      s.add(w);
      String t = w.toLowerCase();
      low.putIfAbsent(t, w);
      pat.putIfAbsent(f(t), w);
    }
    int m = queries.length;
    String[] ans = new String[m];
    for (int i = 0; i < m; ++i) {
      String q = queries[i];
      if (s.contains(q)) {
        ans[i] = q;
        continue;
      }
      q = q.toLowerCase();
      if (low.containsKey(q)) {
        ans[i] = low.get(q);
        continue;
      }
      q = f(q);
      if (pat.containsKey(q)) {
        ans[i] = pat.get(q);
        continue;
      }
      ans[i] = "";
    }
    return ans;
  }
private
  String f(String w) {
    char[] cs = w.toCharArray();
    for (int i = 0; i < cs.length; ++i) {
      char c = cs[i];
      if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u') {
        cs[i] = '*';
      }
    }
    return String.valueOf(cs);
  }
}

```

### CPP

```cpp
class Solution {
public:
  vector<string> spellchecker(vector<string> &wordlist,
                              vector<string> &queries) {
    unordered_set<string> s(wordlist.begin(), wordlist.end());
    unordered_map<string, string> low;
    unordered_map<string, string> pat;
    auto f = [](string &w) {
      string res;
      for (char &c : w) {
        if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u') {
          res += '*';
        } else {
          res += c;
        }
      }
      return res;
    };
    for (auto &w : wordlist) {
      string t = w;
      transform(t.begin(), t.end(), t.begin(), ::tolower);
      if (!low.count(t)) {
        low[t] = w;
      }
      t = f(t);
      if (!pat.count(t)) {
        pat[t] = w;
      }
    }
    vector<string> ans;
    for (auto &q : queries) {
      if (s.count(q)) {
        ans.emplace_back(q);
        continue;
      }
      transform(q.begin(), q.end(), q.begin(), ::tolower);
      if (low.count(q)) {
        ans.emplace_back(low[q]);
        continue;
      }
      q = f(q);
      if (pat.count(q)) {
        ans.emplace_back(pat[q]);
        continue;
      }
      ans.emplace_back("");
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def spellchecker(self, wordlist: List[str], queries: List[str]) -> List[str]: def f(w): t = [] for c in w: t . append("*" if c in "aeiou" else c) return "" . join(t) s = set(wordlist) low, pat = {}, {} for w in wordlist: t = w . lower() low . setdefault(t, w) pat . setdefault(f(t), w) ans = [] for q in queries: if q in s: ans . append(q) continue q = q . lower() if q in low: ans . append(low[q]) continue q = f(q) if q in pat: ans . append(pat[q]) continue ans . append("") return ans

```