Files

83 lines
2.6 KiB
Markdown
Raw Permalink Blame History

This file contains ambiguous Unicode characters

This file contains Unicode characters that might be confused with other characters. If you think that this is intentional, you can safely ignore this warning. Use the Escape button to reveal them.

# [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
## 學習筆記
- 今天學到:
- 卡住與修正:
- 待優化:
---
**總結**:這題的核心在於 ______,適合練習 ______