题目描述
给你一个字符串 word
。如果 word
中同时存在某个字母的小写形式和大写形式,则称这个字母为 特殊字母。
返回 word
中 特殊字母 的数量。
样例
输入:word = "aaAbcBC"
输出:3
解释:
word 中的特殊字母是 'a'、'b' 和 'c'。
输入:word = "abc"
输出:0
解释:
word 中不存在大小写形式同时出现的字母。
输入:word = "abBCab"
输出:1
解释:
word 中唯一的特殊字母是 'b'。
限制
1 <= word.length <= 50
word
仅由小写和大写英文字母组成。
算法
(哈希表) $O(n + |\Sigma|)$
- 将所有字符存储到哈希表中。
- 遍历字符集,在哈希表中判断是否同时出现大小写字母。
时间复杂度
- 构造哈希表的时间复杂度为 $O(n)$。
- 遍历字符集确定答案的时间复杂度为 $O(|\Sigma|)$。
- 故总时间复杂度为 $O(n + |\Sigma|)$。
空间复杂度
- 需要 $O(|\Sigma|)$ 的额外空间存储哈希表。
C++ 代码
class Solution {
public:
int numberOfSpecialChars(string word) {
unordered_set<char> s(word.begin(), word.end());
int ans = 0;
for (char c = 'a'; c <= 'z'; c++)
if (s.count(c) && s.count(c - 'a' + 'A'))
++ans;
return ans;
}
};