# [3227] Vowels Game In A String ## 題目資訊 - **難度**: Medium - **標籤**: Math, String, Brainteaser, Game Theory - **題目連結**: https://leetcode.com/problems/vowels-game-in-a-string/ - **練習日期**: 2025-09-12 - **目標複雜度**: 時間 O(n)、空間 O(1) ## 題目描述 Alice and Bob are playing a game on a string. You are given a string `s`, Alice and Bob will take turns playing the following game where Alice starts **first**: On Alice's turn, she has to remove any **non-empty** substring from `s` that contains an odd number of vowels. On Bob's turn, he has to remove any non-empty substring from `s` that contains an even number of vowels. The first player who cannot make a move on their turn loses the game. We assume that both Alice and Bob play optimally. Return `true` if Alice wins the game, and `false` otherwise. The English vowels are: `a`, `e`, `i`, `o`, and `u`. ## 先備條件與限制 - 輸入限制:n ∈ [1, 10^5]、字符為小寫英文字母 - 回傳/輸出格式:boolean 值,true 表示 Alice 獲勝 ## 解題思路 ### 初步分析 - 類型:博弈論 / 數學 / 腦筋急轉彎 - 關鍵觀察: - Alice 先手,需移除含奇數個母音的子字串 - Bob 後手,需移除含偶數個母音的子字串 - 複雜度目標理由:只需檢查是否存在母音 ### 解法比較 1. 解法A(基準/暴力): - 思路: 發現 Alice 獲勝條件極其簡單 - 正確性: 只需檢查是否存在母音 - 複雜度:O(n) / O(1) ### 常見陷阱 - 邊界:空字串(題目保證 n≥1)、全母音、無母音 - 過度複雜化:誤以為需要複雜的博弈分析 - 計數錯誤:誤以為需要精確計算母音數量 - 大小寫:題目保證小寫字母 ## 測試案例 ### 範例輸入輸出 ``` Input: s = "leetcode" Output: true Explanation: Alice 可以移除 "leetcod"(含3個母音),剩下 "e",Bob 無法移除含偶數母音的子字串 ``` ### 邊界清單 - 全母音字串:Alice 立即移除整個字串獲勝 - 無母音字串:Alice 無法行動敗北 - 單一字符(母音/子音) - 混合字串(含有母音和子音) - 長字串壓力測試 ## 複雜度分析 - 最壞:時間 O(n)、空間 O(1) - 最佳:時間 O(1)(首字符即為母音)、空間 O(1) ## 相關題目 / Follow-up - LeetCode 345: Reverse Vowels of a String - LeetCode 1456: Maximum Number of Vowels in a Substring of Given Length - LeetCode 2062: Count Vowel Substrings of a String ## 學習筆記 - 今天學到: - 卡住與修正: - 待優化: --- **總結**:這題的核心在於 ______,適合練習 ______。