文章目录
题目
标题和出处
标题：判断字符串的两半是否相似
难度
2 级
题目描述
要求
给你一个偶数长度的字符串 s \texttt{s} s。将其拆分成长度相同的两半，前一半为 a \texttt{a} a，后一半为 b \texttt{b} b。
两个字符串相似的前提是它们都含有相同数目的元音（ ‘a’ \texttt{`a'} ‘a’， ‘e’ \texttt{`e'} ‘e’， ‘i’ \texttt{`i'} ‘i’， ‘o’ \texttt{`o'} ‘o’， ‘u’ \texttt{`u'} ‘u’， ‘A’ \texttt{`A'} ‘A’， ‘E’ \texttt{`E'} ‘E’， ‘I’ \texttt{`I'} ‘I’， ‘O’ \texttt{`O'} ‘O’， ‘U’ \texttt{`U'} ‘U’）。注意， s \texttt{s} s 可能同时含有大写和小写字母。
如果 a \texttt{a} a 和 b \texttt{b} b 相似，返回 true \texttt{true} true；否则，返回 false \texttt{false} false。
示例
示例 1：
输入：
s
=
"book"
\texttt{s = "book"}
s = "book"
输出：
true
\texttt{true}
true
解释：
a
=
"b
o
"
\texttt{a = "b}\textbf{o}\texttt{"}
a = "bo" 且
b
=
"
o
k"
\texttt{b = "}\textbf{o}\texttt{k"}
b = "ok"。
a
\texttt{a}
a 中有
1
\texttt{1}
1 个元音，
b
\texttt{b}
b 中也有
1
\texttt{1}
1 个元音。所以，
a
\texttt{a}
a 和
b
\texttt{b}
b 相似。
示例 2：
输入：
s
=
"textbook"
\texttt{s = "textbook"}
s = "textbook"
输出：
false
\texttt{false}
false
解释：
a
=
"t
e
xt"
\texttt{a = "t}\textbf{e}\texttt{xt"}
a = "text" 且
b
=
"b
oo
k"
\texttt{b = "b}\textbf{oo}\texttt{k"}
b = "book" 。
a
\texttt{a}
a 中有
1
\texttt{1}
1 个元音，
b
\texttt{b}
b 中有
2
\texttt{2}
2 个元音。因此，
a
\texttt{a}
a 和
b
\texttt{b}
b 不相似。注意，元音
o
\texttt{o}
o 在
b
\texttt{b}
b 中出现两次，记为
2
\texttt{2}
2 个。
示例 3：
输入：
s
=
"MerryChristmas"
\texttt{s = "MerryChristmas"}
s = "MerryChristmas"
输出：
false
\texttt{false}
false
示例 4：
输入：
s
=
"AbCdEfGh"
\texttt{s = "AbCdEfGh"}
s = "AbCdEfGh"
输出：
true
\texttt{true}
true
数据范围
- 2 ≤ s.length ≤ 1000 \texttt{2} \le \texttt{s.length} \le \texttt{1000} 2≤s.length≤1000
- s.length \texttt{s.length} s.length 是偶数
- s \texttt{s} s 由大写和小写字母组成
解法
思路和算法
由于字符串 s s s 的长度 length \textit{length} length 是偶数，因此可以将 s s s 分成长度相同的两半，前一半的下标范围是 0 0 0 到 length 2 − 1 \dfrac{\textit{length}}{2}-1 2length−1，后一半的下标范围是 length 2 \dfrac{\textit{length}}{2} 2length 到 length − 1 \textit{length}-1 length−1。
分别遍历 s s s 的前一半和后一半，统计两半的元音数量，然后比较两半的元音数量是否相等，即可知道字符串的两半是否相似。
由于 s s s 可能包含大写字母和小写字母，因此在判断每个字母是否是元音时，需要同时考虑大写和小写的情况。
另一种做法是将 s s s 转换成小写字母之后统计两半的元音数量，此时只需要考虑小写的情况。将 s s s 转换成小写字母可以调用编程语言自带的函数或方法，也可以用「转换成小写字母」的做法。
代码
class Solution {
public boolean halvesAreAlike(String s) {
int length = s.length();
int halfLength = length / 2;
int vowelsFirst = 0, vowelsSecond = 0;
for (int i = 0; i < halfLength; i++) {
char c = s.charAt(i);
if (isVowel(c)) {
vowelsFirst++;
}
}
for (int i = halfLength; i < length; i++) {
char c = s.charAt(i);
if (isVowel(c)) {
vowelsSecond++;
}
}
return vowelsFirst == vowelsSecond;
}
public boolean isVowel(char c) {
return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u' || c == 'A' || c == 'E' || c == 'I' || c == 'O' || c == 'U';
}
}
复杂度分析
-
时间复杂度： O ( n ) O(n) O(n)，其中 n n n 是字符串 s s s 的长度。需要遍历字符串一次，计算前一半和后一半的元音数目。
-
空间复杂度： O ( 1 ) O(1) O(1)。