LeetCode Daily Problem P966 Vowel Spellchecker

---

Timeline

timeline

2025-09-15

init

unordered_map and unordered_set achieves O(n) lookup

---

Problem:

P966 Vowel Spellchecker

https://leetcode.cn/problems/vowel-spellchecker/description/?envType=daily-question&envId=2025-09-14

Initially used brute force search, but got TLE, as follows

#include <ctype.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

bool isVowel(char c)
{
        if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u' || c == 'A' || c == 'E' ||
            c == 'I' || c == 'O' || c == 'U') {
                return true;
        }
        return false;
}

int strcomplexcmp(const char *str1, const char *str2)
{
        int len1, len2;
        int i;

        len1 = strlen(str1);
        len2 = strlen(str2);
        for (i = 0; i < len1 && i < len2; i++) {
                if (str1[i] == str2[i]) {
                        continue;
                } else if (isVowel(str1[i]) && isVowel(str2[i])) {
                        continue;
                } else if (tolower(str1[i]) == tolower(str2[i])) {
                        continue;
                } else {
                        return str1[i] - str2[i];
                }
        }
        if (str1[i] == '\0' && str2[i] == '\0') {
                return 0;
        } else {
                return str1[i] - str2[i];
        }
}

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
char **spellchecker(char **wordlist, int wordlistSize, char **queries, int queriesSize,
                    int *returnSize)
{
        char **returnArray;
        char *totally_matched;
        char *case_matched;
        char *vowel_matched;
        char *complex_matched;

        *returnSize = queriesSize;
        returnArray = (char **)malloc(queriesSize * sizeof(char *));

        for (int i = 0; i < queriesSize; i++) {
                totally_matched = NULL;
                case_matched = NULL;
                vowel_matched = NULL;
                complex_matched = NULL;

                for (int j = 0; j < wordlistSize; j++) {
                        if (strcmp(wordlist[j], queries[i]) == 0 && totally_matched == NULL) {
                                totally_matched = wordlist[j];
                                break;
                        } else if (strcasecmp(wordlist[j], queries[i]) == 0 &&
                                   case_matched == NULL) {
                                case_matched = wordlist[j];
                        } else if (strcomplexcmp(wordlist[j], queries[i]) == 0 &&
                                   complex_matched == NULL) {
                                complex_matched = wordlist[j];
                        }
                }

                if (totally_matched) {
                        returnArray[i] = strdup(totally_matched);
                } else if (case_matched) {
                        returnArray[i] = strdup(case_matched);
                } else if (complex_matched) {
                        returnArray[i] = strdup(complex_matched);
                } else {
                        returnArray[i] = strdup("");
                }
        }
        return returnArray;
}

int main()
{
        char *wordlist[] = { "KiTe", "kite", "hare", "Hare" };
        int wordlistSize = 4;
        char *queries[] = { "kite", "Kite", "KiTe", "Hare", "HARE",
                            "Hear", "hear", "keti", "keet", "keto" };

        int queriesSize = 10;
        int returnSize = queriesSize;
        char **returnArray;
        returnArray = spellchecker(wordlist, wordlistSize, queries, queriesSize, &returnSize);
        for (int i = 0; i < returnSize; i++) {
                printf("%s, ", returnArray[i]);
                free(returnArray[i]);
        }
        free(returnArray);
}

Using hash table lookup reduces from O(n^2) to O(n), below is the officially recommended C++ implementation

#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <ctype.h>
using namespace std;

class Solution {
    private:
        // Store unprocessed strings
        unordered_set<string> words_perfect;
        // Store mapping of lowercased strings to original strings
        unordered_map<string, string> words_cap;
        // Store mapping of strings with vowels replaced by * to original strings
        unordered_map<string, string> words_vow;

        //Replace all vowels with *
        string devowel(string word)
        {
                string ans;
                for (char c : word) {
                        ans += isVowel(c) ? '*' : c;
                }
                return ans;
        }
        // Determine whether it is a vowel letter
        bool isVowel(char c)
        {
                c = tolower(c);
                return (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u');
        }

        string match(string query)
        {
                //Exact match
                if (words_perfect.count(query)) {
                        return query;
                }
                // Case
                string queryL;
                for (char c : query) {
                        queryL += tolower(c);
                }
                if (words_cap.count(queryL)) {
                        return words_cap[queryL];
                }
                // After converting all to lowercase, find vowel letters
                string queryLV = devowel(queryL);
                if (words_vow.count(queryLV)) {
                        return words_vow[queryLV];
                }

                return "";
        }

    public:
        vector<string> spellchecker(vector<string> &wordlist, vector<string> &queries)
        {
                //Fill set and two maps
                for (string word : wordlist) {
                        words_perfect.insert(word);
                        string wordlow;
                        for (char c : word) {
                                wordlow += tolower(c);
                        }
                        if (!words_cap.count(wordlow)) {
                                words_cap[wordlow] = word;
                        }
                        // After converting all to lowercase, then convert vowel letters to *
                        string wordlowDV = devowel(wordlow);
                        if (!words_vow.count(wordlowDV)) {
                                words_vow[wordlowDV] = word;
                        }
                }

                vector<string> ans;
                for (string query : queries) {
                        ans.push_back(match(query));
                }
                return ans;
        }
};

Average time complexity

Operation	unordered_set	unordered_map
Insert	O(1)	O(1)
Search	O(1)	O(1)
Delete	O(1)	O(1)

• HereO(1)isAverage complexity, assuming the hash function is evenly distributed and collisions are few.
• Main advantages:Faster than std::set/std::map (based on red-black tree), red-black tree lookup is O(log n).

Worst-case time complexity

• In the worst case, if all elements are hashed to the same bucket (hash collision), it degenerates intolinked list：
  • lookup, insertion, deletion all becomeO(n)。
• C++ standard library implementations typically usebucket + linked list (or red-black tree), when there are too many collisions, the linked list is converted into a red-black tree, thus reducing the worst-case complexity:
  • After C++11, unordered_map/unordered_set’s single bucket linked list length exceeds a certain threshold (usually 8), it will be converted into a red-black tree, ensuring worst-case complexityO(log n)。

---

Space complexity

• Average O(n), storing hash table and elements.
• Hash table requires an extra bucket array, occupying extra space.