3227. 字符串中的元音游戏

Medium

题目描述

Alice 和 Bob 正在玩一个字符串游戏。

给你一个字符串 s，Alice 和 Bob 将轮流进行以下游戏，其中 Alice 先手：

• 在 Alice 的回合中，她必须从 s 中移除任何包含奇数个元音的非空子串。
• 在 Bob 的回合中，他必须从 s 中移除任何包含偶数个元音的非空子串。

第一个无法在自己回合中进行操作的玩家败北。我们假设 Alice 和 Bob 都会最优地进行游戏。

如果 Alice 获胜，返回 true，否则返回 false。

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

示例 1：

输入：s = "leetcoder"
输出：true
解释：
Alice 可以按以下方式获胜：
- Alice 先手，她可以删除 s = "leetcoder" 中下划线部分的子串，包含 3 个元音。结果字符串为 s = "der"。
- Bob 第二轮，他可以删除 s = "der" 中下划线部分的子串，包含 0 个元音。结果字符串为 s = "er"。
- Alice 第三轮，她可以删除整个字符串 s = "er"，包含 1 个元音。
- Bob 第四轮，由于字符串为空，Bob 无法进行有效操作。所以 Alice 获胜。

示例 2：

输入：s = "bbcd"
输出：false
解释：
Alice 在第一轮无法进行有效操作，所以 Alice 败北。

约束条件：

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

解题思路

这是一个博弈论问题，需要分析游戏的获胜条件。

关键观察：

1. 如果字符串中没有元音字母：Alice 无法移除任何子串（因为她需要移除包含奇数个元音的子串），所以 Bob 获胜。

2. 如果字符串中元音字母总数为奇数：Alice 可以在第一轮直接移除整个字符串获胜（整个字符串包含奇数个元音）。

3. 如果字符串中元音字母总数为偶数且大于0：这是关键情况。Alice 需要移除包含奇数个元音的子串，这样剩余字符串的元音个数就变成了奇数。然后轮到 Bob，他需要移除包含偶数个元音的子串。

通过分析可以发现，只要字符串中存在元音字母，Alice 总是可以获胜的：

• 如果总元音数为奇数，Alice 直接移除整个字符串
• 如果总元音数为偶数，Alice 可以移除任意一个元音字母（这是包含1个元音的子串），使得剩余字符串的元音数变为奇数，然后 Bob 面临奇数个元音的情况

因此，Alice 获胜的充要条件是：字符串中至少包含一个元音字母。

代码实现

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

class Solution:
    def doesAliceWin(self, s: str) -> bool:
        for c in s:
            if c in 'aeiou':
                return True
        return False

public class Solution {
    public bool DoesAliceWin(string s) {
        foreach (char c in s) {
            if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u') {
                return true;
            }
        }
        return false;
    }
}

/**
 * @param {string} s
 * @return {boolean}
 */
var doesAliceWin = function(s) {
    for (let c of s) {
        if ('aeiou'.includes(c)) {
            return true;
        }
    }
    return false;
};

复杂度分析