題目描述:給定字串 s,僅將其中的母音字母(a、e、i、o、u,大小寫均算)位置對調,其餘字元保持不動。
解題思路:使用雙指標從兩端向中間靠攏。左指標找到第一個母音,右指標找到第一個母音,兩者交換後繼續向內移動,直到兩指標相遇。用雜湊集合存母音字元方便 O(1) 查詢。只需一次線性掃描,時間 O(n),空間 O(1)(不計輸出)。
時間複雜度: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) 空間,不如雙指標簡潔。