345. Reverse Vowels of a String

📘 題目敘述

給定一個字串 s，請將字串中的所有母音（vowels）反轉後回傳。

母音包含：'a', 'e', 'i', 'o', 'u'（以及對應的大寫）。

條件限制

1 ≤ s.length ≤ 3 * 10^5
s 由可列印的 ASCII 字元組成

🧠 解題思路

我這題的想法是把「母音的位置」先全部抓出來，然後再反過來填回去。

具體來說我做了兩件事：

掃描整個字串，把所有母音出現的位置記下來
再用「反向對應」的方式，把母音依序寫回原本的位置

這樣我就不需要在掃描時馬上交換字元，而是先收集資訊，再一次完成替換。

所有變數

revvow：一個 2 列的 vector，用來記錄所有母音資訊
- revvow[0]：母音出現的位置（index）
- revvow[1]：母音是哪一個（用它在 vowels 裡的索引表示）
n：字串 s 的長度
vowels：母音清單（包含大小寫），用來判斷是否為母音，以及最後替換時查表用
rev：母音總數（也就是 revvow[0].size()）
pos：要被替換的位置（第 k 個母音所在的 index）
vpos：反轉後要放進來的母音（透過 vowels 的索引查出）

第一段：找出所有母音的位置與種類

我會從左到右掃描字串 s：

對每個字元 s[i]，再去比對 vowels 清單
如果 s[i] 是母音：
- 把位置 i 存到 revvow[0]
- 把它在 vowels 清單中的索引 j 存到 revvow[1]

這樣做完之後，我就知道母音總共有幾個、每個母音的位置在哪裡，以及每個母音原本是哪一個字元。

第二段：用「反向對應」把母音寫回去

母音反轉的意思是：

第 0 個母音的位置，要放「最後一個母音」
第 1 個母音的位置，要放「倒數第二個母音」
以此類推

所以我用 k 從 0 到 rev - 1：

pos = revvow[0][k]：第 k 個母音的位置
vpos = revvow[1][rev - 1 - k]：反轉後要放的母音
最後把 s[pos] 改成 vowels[vpos]

這個寫法的直覺總結

我先把母音挑出來排成一列
再把這列母音反過來
最後照原本母音的位置依序填回去

因此非母音的位置完全不會被動到，符合題目要求。

💻 程式碼實作

class Solution {
public:
    string reverseVowels(string s) {
        vector<vector<int>> revvow(2); // revvow[0]是位置，revvow[1]是母音
        int n = s.size();
        int pos, vpos;
        vector<char> vowels = {'A', 'E', 'I', 'O', 'U', 'a', 'e', 'i', 'o', 'u'};
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < vowels.size(); j++) {
                if (s[i] == vowels[j]) {
                    revvow[0].push_back(i);
                    revvow[1].push_back(j);
                }
            }
        }
        int rev = revvow[0].size();
        for (int k = 0; k < rev; k++) {
            pos = revvow[0][k];
            vpos = revvow[1][rev - 1 - k];
            s[pos] = vowels[vpos];
        }
        return s;
    }
};

🔗 題目連結

https://leetcode.com/problems/reverse-vowels-of-a-string/