给定一个偶数长度的字符串s。把这个字符串分成长度相等的两半,前半部分a,后半部分b。
如果两个字符串的元音字母数目相同('a'、'e'、'i'、'o'、'u'、'A'、'E'、'I'、'O'、'U'),那么它们就是相同的。区分大小写。
如果a和b相同,则返回true,否则返回false。
双指针,两个map解决。时间复杂度O(n)。不需要用到map,因为只需要统计元音字母的总数量,不需要区分不同的元音字母,两个count前后计数即可。然后用一个set来存储需要查找的元音字母。
重新回忆一下下边这张表:(链接:代码随想录
class Solution {
public:
bool halvesAreAlike(string s) {
set<char> vowels = {'a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U'};
int counta = 0, countb = 0;
for (int i = 0; i < s.size() / 2; ++i) {
int j = i + s.size() / 2;
if (vowels.find(s[i]) != vowels.end()) {
counta++;
}
if (vowels.find(s[j]) != vowels.end()) {
countb++;
}
}
return counta == countb;
}
};
1. **初始化元音集合**: 这是一个常数时间操作,因为集合中的元素数量是固定的(10个元音字母)。
2. **遍历字符串**: 代码遍历了字符串 `s` 的每个字符一次。因此,这部分的时间复杂度与字符串的长度 `n` 线性相关,即 `O(n)`。
3. **查找集合中的元素**: 每次遍历时,代码都会检查当前字符是否为元音字母。在`set`中查找元素的时间复杂度是 `O(log m)`,其中 `m` 是集合中元素的数量。由于元音字母的数量是固定的(10个),这可以近似视为常数时间操作,即 `O(1)`。
综上所述,总的时间复杂度主要由字符串的遍历决定,即为 `O(n)`。
1. **元音集合**: 这个集合包含了10个元音字母,是一个常数空间占用,即 `O(1)`。
2. **计数器**: 使用了两个整型变量 `count1` 和 `count2` 来计数,这也是常数空间占用。
因此,总的空间复杂度为 `O(1)`,也就是说,空间复杂度是常数级的。
综上,这段代码的时间复杂度是 `O(n)`,空间复杂度是 `O(1)`。