1704. 判断字符串的两半是否相似
1704. 判断字符串的两半是否相似
题目
You are given a string s
of even length. Split this string into two halves of equal lengths, and let a
be the first half and b
be the second half.
Two strings are alike if they have the same number of vowels ('a'
, 'e'
, 'i'
, 'o'
, 'u'
, 'A'
, 'E'
, 'I'
, 'O'
, 'U'
). Notice that s
contains uppercase and lowercase letters.
Return true
ifa
andb
are alike. Otherwise, return false
.
Example 1:
Input: s = "book"
Output: true
Explanation: a = "b o " and b = "o k". a has 1 vowel and b has 1 vowel. Therefore, they are alike.
Example 2:
Input: s = "textbook"
Output: false
Explanation: a = "t e xt" and b = "b oo k". a has 1 vowel whereas b has 2. Therefore, they are not alike.
Notice that the vowel o is counted twice.
Constraints:
2 <= s.length <= 1000
s.length
is even.s
consists of uppercase and lowercase letters.
题目大意
给你一个偶数长度的字符串 s
。将其拆分成长度相同的两半,前一半为 a
,后一半为 b
。
两个字符串 相似 的前提是它们都含有相同数目的元音('a'
,'e'
,'i'
,'o'
,'u'
,'A'
,'E'
,'I'
,'O'
,'U'
)。注意,s
可能同时含有大写和小写字母。
如果 a
和 b
相似,返回 true
;否则,返回 false
。
示例 1:
输入: s = "book"
输出: true
解释: a = "bo " 且 b = "o k" 。a 中有 1 个元音,b 也有 1 个元音。所以,a 和 b 相似。
示例 2:
输入: s = "textbook"
输出: false
解释: a = "te xt" 且 b = "boo k" 。a 中有 1 个元音,b 中有 2 个元音。因此,a 和 b 不相似。
注意,元音 o 在 b 中出现两次,记为 2 个。
提示:
2 <= s.length <= 1000
s.length
是偶数s
由 大写和小写 字母组成
解题思路
使用一个函数
isVowel
来判断字符是否为元音。元音字母包括a, e, i, o, u
(大小写均需考虑)。双指针遍历:
- 使用双指针分别从字符串的左侧和右侧向中间移动。
- 左指针统计左半部分元音数量,右指针统计右半部分元音数量。
当两指针相遇后统计结束,只需比较两部分的元音数量是否相等。
复杂度分析
- 时间复杂度:
O(n)
,遍历字符串一次(n
为字符串长度)。 - 空间复杂度:
O(1)
,只使用了常数额外空间。
代码
/**
* @param {string} s
* @return {boolean}
*/
var halvesAreAlike = function (s) {
// 判断是否为元音
const isVowel = (char) => 'aeiouAEIOU'.includes(char);
let leftVowels = 0; // 左半部分元音计数
let rightVowels = 0; // 右半部分元音计数
let left = 0; // 左指针
let right = s.length - 1; // 右指针
while (left < right) {
// 左半部分统计
if (isVowel(s[left++])) {
leftVowels++;
}
// 右半部分统计
if (isVowel(s[right--])) {
rightVowels++;
}
}
// 比较元音数量是否相等
return leftVowels == rightVowels;
};