3227. 字符串元音游戏

题目描述

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

给你一个字符串 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 仅由小写英文字母组成。

解法

方法一：脑筋急转弯

我们不妨记字符串中元音字母的个数为 $k$。

如果 $k = 0$，即字符串中没有元音字母，那么小红无法移除任何子字符串，小明直接获胜。

如果 $k$ 为奇数，那么小红可以移除整个字符串，小红直接获胜。

如果 $k$ 为偶数，那么小红可以移除 $k - 1$ 个元音字母，此时剩下一个元音字母，小明无法移除任何子字符串，小红直接获胜。

综上所述，如果字符串中包含元音字母，那么小红获胜，否则小明获胜。

时间复杂度 $O(n)$，其中 $n$ 为字符串 $s$ 的长度。空间复杂度 $O(1)$。

Python3JavaC++GoTypeScript

class Solution:
    def doesAliceWin(self, s: str) -> bool:
        vowels = set("aeiou")
        return any(c in vowels for c in s)

class Solution {
    public boolean doesAliceWin(String s) {
        for (int i = 0; i < s.length(); ++i) {
            if ("aeiou".indexOf(s.charAt(i)) != -1) {
                return true;
            }
        }
        return false;
    }
}

class Solution {
public:
    bool doesAliceWin(string s) {
        string vowels = "aeiou";
        for (char c : s) {
            if (vowels.find(c) != string::npos) {
                return true;
            }
        }
        return false;
    }
};

func doesAliceWin(s string) bool {
    vowels := "aeiou"
    for _, c := range s {
        if strings.ContainsRune(vowels, c) {
            return true
        }
    }
    return false
}

function doesAliceWin(s: string): boolean {
    const vowels = 'aeiou';
    for (const c of s) {
        if (vowels.includes(c)) {
            return true;
        }
    }
    return false;
}

3227. 字符串元音游戏

题目描述

解法

方法一：脑筋急转弯

评论