LeetCode 345. 反轉字符串中的元音字母：雙指針原地交換

LeetCode 345. 反轉字符串中的元音字母

題目描述

給定字符串 s，僅反轉其中的元音字母（a, e, i, o, u 不分大小寫），其他字符位置不變。

範例

• "hello" → "holle"
• "leetcode" → "leotcede"

雙指針法

左右指針 i=0, j=n-1 向中間掃描：

1. i 右移直到指向元音。
2. j 左移直到指向元音。
3. 若 i < j，交換 s[i] 和 s[j]，i++, j--。
4. 重複直到 i >= j。

代碼實現

bool isVowel(char c) {
    c = tolower(c);
    return c=='a' || c=='e' || c=='i' || c=='o' || c=='u';
}

char* reverseVowels(char* s) {
    int i = 0, j = strlen(s) - 1;
    while (i < j) {
        while (i < j && !isVowel(s[i])) i++;
        while (i < j && !isVowel(s[j])) j--;
        if (i < j) {
            char tmp = s[i];
            s[i] = s[j];
            s[j] = tmp;
            i++; j--;
        }
    }
    return s;
}

優化點

• 提取 isVowel 輔助函數，避免冗長條件判斷重複。
• 使用 tolower 統一大小寫判斷。
• 雙重 while 循環跳過非元音，邏輯清晰無冗餘分支。

複雜度分析

• 時間複雜度：O(n)，單次遍歷。
• 空間複雜度：O(1)，原地修改。

總結

反轉元音字母是雙指針「對撞指針」模式的典型應用：左右掃描、跳過無關字符、相遇交換。同模式適用於「反轉字符串、移除元素、三數之和」等問題。