时间轴

2025-09-15

init

题目：

P966 元音拼写检查器

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
#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++写法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#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)，存储哈希表和元素。
  • 哈希表需要额外的桶数组，占用额外空间。