力扣(LeetCode)1704. 判断字符串的两半是否相似(C++)

双指针

设置双指针 $i、j$，$i$ 从 $0$ 到 $\frac{s.size()}{2}-1$ ， $j$ 从 $\frac{s.size()}{2}$ 到 $s.size()$。当 $i$ 指向元音， $cnt++$，当 $j$ 指向元音 $cnt--$。由于 $s.size()$ 是偶数，双指针的遍历同时结束。遍历结束，如果 $cnt=0$ 两半相似，否则不相似。

代码展示

class Solution {
public:
    bool halvesAreAlike(string s) {
        int len = s.size()/2;//子串长度
        int cnt = 0;
        string h = "aeiouAEIOU" ;
        for(int i =0,j=len;i<len;i++,j++){
            if(h.find(s[i])!=string::npos) cnt++;
            if(h.find(s[j])!=string::npos) cnt--;
        }
        if(cnt) return false;
        return true;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

博主致语

理解思路很重要！
欢迎读者在评论区留言，作为日更博主，看到就会回复的。

AC

复杂度分析

1. 时间复杂度: $O(n)$， $n$ 是字符串 $s$ 的长度，一次遍历 $s$ 的时间复杂度 $O(n)$ 。
2. 空间复杂度: $O(|C|)$。$|C|=10$，是元音字符串 $h$ 的长度。