README.md

comments	difficulty	edit_url	rating	source	tags
true	中等	https://github.com/doocs/leetcode/edit/main/solution/3200-3299/3227.Vowels%20Game%20in%20a%20String/README.md	1451	第 407 场周赛 Q2	脑筋急转弯 数学 字符串 博弈

3227. 字符串元音游戏

English Version

题目描述

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

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

解法

方法一：脑筋急转弯

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

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

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

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

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

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

Python3

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

Java

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;
    }
}

C++

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

Go

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

TypeScript

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