字符串元音游戏

100335. 字符串元音游戏

小红和小明在玩一个字符串元音游戏。

给你一个字符串 s，小红和小明将轮流参与游戏，小红先开始：

在小红的回合，她必须移除 s 中包含奇数个元音的任意非空子字符串。
在小明的回合，他必须移除 s 中包含偶数个元音的任意非空子字符串。

第一个无法在其回合内进行移除操作的玩家输掉游戏。假设小红和小明都采取 最优策略 。

如果小红赢得游戏，返回 true，否则返回 false。

英文元音字母包括：a, e, i, o, 和 u。

示例 1：

输入： s = "leetcoder"

输出： true

解释：
小红可以执行如下移除操作来赢得游戏：

小红先手，她可以移除加下划线的子字符串 s = "leetcoder"，其中包含 3 个元音。结果字符串为 s = "der"。
小明接着，他可以移除加下划线的子字符串 s = "der"，其中包含 0 个元音。结果字符串为 s = "er"。
小红再次操作，她可以移除整个字符串 s = "er"，其中包含 1 个元音。
又轮到小明，由于字符串为空，无法执行移除操作，因此小红赢得游戏。

示例 2：

输入： s = "bbcd"

输出： false

解释：
小红在她的第一回合无法执行移除操作，因此小红输掉了游戏。

提示：

1 <= s.length <= 10⁵
s 仅由小写英文字母组成。

原站题解

去查看

上次编辑到这里，代码来自缓存点击恢复默认模板

class Solution { public: bool doesAliceWin(string s) { } };

golang 解法, 执行用时: 15 ms, 内存消耗: 6.3 MB, 提交时间: 2024-07-22 22:58:59

func doesAliceWin(s string) bool {
	return strings.ContainsAny(s, "aeiou")
}

java 解法, 执行用时: 7 ms, 内存消耗: 44.4 MB, 提交时间: 2024-07-22 22:58:47

class Solution {
    public boolean doesAliceWin(String s) {
        for (char c : s.toCharArray()) {
            if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u') {
                return true;
            }
        }
        return false;
    }
}

cpp 解法, 执行用时: 45 ms, 内存消耗: 17 MB, 提交时间: 2024-07-22 22:58:35

class Solution {
public:
    bool doesAliceWin(string s) {
        return ranges::any_of(s, [](char c) {
            return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
        });
    }
};

python3 解法, 执行用时: 67 ms, 内存消耗: 16.8 MB, 提交时间: 2024-07-22 22:58:20

'''
分类讨论：

如果 s 不包含任何元音，小红输。
如果 s 包含奇数个元音，小红可以直接把整个 s 移除，小红赢。
如果 s 包含正偶数个元音，由于偶数减奇数等于奇数，小红移除任意包含奇数个元音的子串后，剩余元音个数仍然为奇数。
由于奇数减偶数还是奇数，所以无论小明怎么操作，仍然会剩下奇数个元音，此时小红可以直接把整个 s 移除，小红赢。
所以只要 s 包含元音，就返回 true，否则返回 false。
'''
class Solution:
    def doesAliceWin(self, s: str) -> bool:
        return any(c in "aeiou" for c in s)

上一题

下一题

详情