题目

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

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

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

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

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

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

示例 1：

输入： s = "leetcoder"

输出： true

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

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

示例 2：

输入： s = "bbcd"

输出： false

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

提示：

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

解题思路

情况一：字符串 s 中一个元音都没有

例如 s = "rhythm"。

1. 轮到小红。她需要移除一个有奇数（1, 3, 5...）个元音的子串。
2. 但是字符串 s 里根本没有元音。所以 s 的任何非空子串都只包含辅音，元音数量为 0。
3. 数字 0 是一个偶数。
4. 因此，小红找不到任何一个符合她要求的子串。
5. 结论：小红在第一回合就无法行动，直接输掉游戏。

所以，如果字符串 s 中不含任何元音，小红必败。

情况二：字符串 s 中至少有一个元音

现在情况变得有趣了。只要字符串里有元音，小红就总能找到一个可以移除的子串。最简单的例子：她可以选择只包含单个元音字母的子串（比如 s="leetcode"，她可以只移除子串"e"）。这个子串包含 1 个元音，1 是奇数，这是一个合法的操作。

• 子情况 2a：s 的总元音数是奇数
  • 小红的最优策略就是直接移除整个字符串 s。
  • 这一步是合法的，因为 s 元音总数是奇数。
  • 小明面对空字符串，无法行动，小明输。
  • 结论：小红必胜。
• 子情况 2b：s 的总元音数是偶数 (且 > 0)
  • 小红不能一次性移除整个字符串 s 了。她必须移除 s 的一个真子集。
  • 小红的策略是：她只需要移除一个包含 1 个元音的子串（例如，只包含第一个元音字母的子串）。
  • 移除前：s 的总元音数是偶数。
  • 移除后：剩下的字符串 s' 的总元音数变成了 (偶数 - 1)，结果一定是奇数。
  • 现在轮到小明了。他面对一个总元音数为奇数的字符串 s'。
  • 小明的规则是移除一个包含偶数个元音的子串。
  • 他从一个总元音数为奇数的 s' 中，移走一个元音数为偶数的子串后，剩下的字符串 s'' 的总元音数是多少呢？ (奇数 - 偶数)，结果仍然是奇数！
  • 关键发现：无论小明怎么操作，只要他能操作，他留给小红的必定是一个总元音数为奇数的字符串。
  • 现在又轮到小红了！她面对一个总元音数为奇数的字符串 s''。这回到了我们刚刚分析的 子情况 2a。
  • 小红的最优策略是：直接移除整个 s''，赢得比赛。
  • 结论：小红也必胜。

把以上所有情况整合起来：

1. 如果字符串 s 中没有元音 -> 小红第一步就卡住了 -> 小红输。
2. 如果字符串 s 中有至少一个元音 -> 无论总元音数是奇数还是偶数，小红都有一套必胜的策略 -> 小红赢。

所以，这道复杂的博弈论问题，最终简化成了一个极其简单的问题：

“字符串 s 中是否存在至少一个元音字母？”

• 如果存在 -> true (小红赢)
• 如果不存在 -> false (小红输)

具体代码

class Solution {
public:
    bool doesAliceWin(string s) {
        // s.cbegin() 和 s.cend() 是常数迭代器
        return any_of(s.cbegin(), s.cend(), [](char c) {
            return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
        });
    }
};

或者

class Solution {
public:
    bool doesAliceWin(string s) {
        return s.find_first_of("aeiou") != string::npos;
    }
};