leetcode每日一题 P966 元音拼写检查器

---

时间轴

时间轴

2025-09-15

init

unordered_map和unordered_set实现O(n)查找

---

题目：

P966 元音拼写检查器

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

最开始使用暴力搜索的方法，但是 TLE 了，如下

#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);
}

用哈希表查找能从 O(n^2)降低到 O(n)，下面是官方推荐的 C++写法

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

class Solution {
    private:
        // 存储未处理的字符串
        unordered_set<string> words_perfect;
        // 存储小写后的字符串和原字符串的映射
        unordered_map<string, string> words_cap;
        // 存储将元音字母都转换为*的字符串和原字符串的映射
        unordered_map<string, string> words_vow;

        //将元音字母都转换为*
        string devowel(string word)
        {
                string ans;
                for (char c : word) {
                        ans += isVowel(c) ? '*' : c;
                }
                return ans;
        }
        // 判断是否是否是元音字母
        bool isVowel(char c)
        {
                c = tolower(c);
                return (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u');
        }

        string match(string query)
        {
                //完全匹配
                if (words_perfect.count(query)) {
                        return query;
                }
                // 大小写
                string queryL;
                for (char c : query) {
                        queryL += tolower(c);
                }
                if (words_cap.count(queryL)) {
                        return words_cap[queryL];
                }
                // 都转为小写字母后，查找元音字母
                string queryLV = devowel(queryL);
                if (words_vow.count(queryLV)) {
                        return words_vow[queryLV];
                }

                return "";
        }

    public:
        vector<string> spellchecker(vector<string> &wordlist, vector<string> &queries)
        {
                //填充set和两个map
                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;
                        }
                        // 都转成小写字母后再将元音字母转为*
                        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;
        }
};

平均时间复杂度

操作	unordered_set	unordered_map
插入	O(1)	O(1)
查找	O(1)	O(1)
删除	O(1)	O(1)

• 这里的 O(1) 是 平均复杂度，假设哈希函数分布均匀，冲突较少。
• 主要优点：比 std::set/std::map（基于红黑树）快，红黑树的查找是 O(log n)。

最坏情况时间复杂度

• 最坏情况下，如果所有元素都被哈希到同一个桶（hash collision），退化成 链表：
  • 查找、插入、删除都变为 O(n)。
• C++ 标准库实现通常用 桶 + 链表（或红黑树），在冲突过多时，会把链表转换成红黑树，从而降低最坏情况复杂度：
  • C++11 以后，unordered_map/unordered_set 的单个桶链表长度超过一定阈值（通常是 8），会转换成红黑树，保证最坏复杂度 O(log n)。

---

空间复杂度

• 平均 O(n)，存储哈希表和元素。
• 哈希表需要额外的桶数组，占用额外空间。