题目描述
小红和小明在玩一个字符串元音游戏。
给你一个字符串 s
,小红和小明将轮流参与游戏,小红 先 开始:
- 在小红的回合,她必须移除
s
中包含 奇数 个元音的任意 非空
子字符串
。 - 在小明的回合,他必须移除
s
中包含 偶数 个元音的任意 非空
子字符串
。
第一个无法在其回合内进行移除操作的玩家输掉游戏。假设小红和小明都采取 最优策略。
如果小红赢得游戏,返回 true
,否则返回 false
。
英文元音字母包括:a
,e
,i
,o
和 u
。
样例
输入: s = "leetcoder"
输出: true
解释:
小红可以执行如下移除操作来赢得游戏:
小红先手,她可以移除加下划线的子字符串 s = "leetcoder",其中包含 3 个元音。
结果字符串为 s = "der"。
小明接着,他可以移除加下划线的子字符串 s = "der",其中包含 0 个元音。
结果字符串为 s = "er"。
小红再次操作,她可以移除整个字符串 s = "er",其中包含 1 个元音。
又轮到小明,由于字符串为空,无法执行移除操作,因此小红赢得游戏。
输入: s = "bbcd"
输出: false
解释:
小红在她的第一回合无法执行移除操作,因此小红输掉了游戏。
限制
1 <= s.length <= 10^5
s
仅由小写英文字母组成。
算法
(思维题) $O(n)$
- 注意到,如果一开始字符串中存在奇数个元音字符,则小红可以移除全部字符赢得游戏。
- 如果一开始字符串中存在元音字符且为偶数个,则小红一定可以移除一个子串使得字符串中仅剩一个元音字符,然后再次将最后一个元音字符的字符串也移除掉,赢得游戏。
- 如果一开始字符串中就没有元音字符,则小红输掉了游戏。
时间复杂度
- 遍历字符串一次,故时间复杂度为 $O(n)$。
空间复杂度
- 仅需要常数的额外空间。
C++ 代码
class Solution {
public:
bool doesAliceWin(string s) {
for (char c : s)
if (c == 'a' || c == 'e' || c == 'i'
|| c == 'o' || c == 'u')
return true;
return false;
}
};