解題說明
Reverse Vowels of a String
題目描述:給定字串 s,僅將其中的母音字母(a、e、i、o、u,大小寫均算)位置對調,其餘字元保持不動。
解題思路:使用雙指標從兩端向中間靠攏。左指標找到第一個母音,右指標找到第一個母音,兩者交換後繼續向內移動,直到兩指標相遇。用雜湊集合存母音字元方便 O(1) 查詢。只需一次線性掃描,時間 O(n),空間 O(1)(不計輸出)。
C++ 解法
複雜度分析
時間複雜度:O(n) — 左右指標合計最多走過整個字串一次。
空間複雜度:O(1) — 母音集合大小固定(最多 10 個字元),字串原地修改。
虛擬碼
1. Define vowel set = {a, e, i, o, u, A, E, I, O, U}
2. left = 0, right = len(s) - 1
3. While left < right:
a. Advance left until s[left] is a vowel
b. Advance right until s[right] is a vowel
c. If left < right: swap s[left] and s[right], left++, right--
4. Return s其他解法
收集母音後反向填入:先掃描一遍收集所有母音字元存入陣列,再反向掃描將母音填回原位置。需要 O(n) 額外空間,但邏輯直觀易懂。
Stack:將所有母音壓入 stack,再掃描一次遇到母音位置就 pop 填入。同樣 O(n) 空間,不如雙指標簡潔。
延伸思考
- 若要求反轉所有子音而非母音,雙指標邏輯是否相同?
- 如何將此題擴展為「反轉所有滿足特定條件的字元」的通用函式?
- Unicode 字串(如帶重音的 é、ü)如何正確判斷母音?