LeetCode 345. 反轉字符串中的元音字母：雙指針原地算法 Java 實現

LeetCode 345. 反轉字符串中的元音字母：雙指針原地算法 Java 實現

題目描述

編寫函數，接收一個字符串，僅反轉其中的元音字母 (a, e, i, o, u, A, E, I, O, U)，其他字符位置不變。

示例 1："hello" → "holle" (e, o 互換)

示例 2："leetcode" → "leotcede" (e, o, e, e → e, e, o, e)

核心思路：雙指針原地交換

字符串不可變，轉 char[] 操作。左右雙指針向中間掃描，遇到元音則交換，非元音則移動指針。

Java 實現 (標準解法)

public String reverseVowels(String s) {
    if (s == null || s.length() <= 1) return s;
    
    // 元音查找集：O(1) 判斷
    Set vowels = new HashSet<>(Arrays.asList('a','e','i','o','u','A','E','I','O','U'));
    // 或用 boolean[128] 數組更快 (ASCII)
    // boolean[] isVowel = new boolean[128];
    // for (char c : "aeiouAEIOU".toCharArray()) isVowel[c] = true;
    
    char[] chars = s.toCharArray();
    int left = 0, right = chars.length - 1;
    
    while (left < right) {
        // 左指針找元音
        while (left < right && !vowels.contains(chars[left])) left++;
        // 右指針找元音
        while (left < right && !vowels.contains(chars[right])) right--;
        
        // 交換
        if (left < right) {
            char temp = chars[left];
            chars[left] = chars[right];
            chars[right] = temp;
            left++;
            right--;
        }
    }
    return new String(chars);
}

優化版：boolean 數組替代 HashSet (極致性能)

public String reverseVowels(String s) {
    if (s == null || s.length() <= 1) return s;
    
    // ASCII 範圍內 boolean 數組查找最快，無哈希開銷
    boolean[] isVowel = new boolean[128];
    for (char c : "aeiouAEIOU".toCharArray()) isVowel[c] = true;
    
    char[] chars = s.toCharArray();
    int left = 0, right = chars.length - 1;
    
    while (left < right) {
        while (left < right && !isVowel[chars[left]]) left++;
        while (left < right && !isVowel[chars[right]]) right--;
        
        if (left < right) {
            char temp = chars[left];
            chars[left] = chars[right];
            chars[right] = temp;
            left++;
            right--;
        }
    }
    return new String(chars);
}

複雜度分析

• 時間：O(n) — 單次遍歷，每字符最多訪問常數次
• 空間：O(n) — char[] 複製 (Java 字符串不可變) + O(1) 輔助空間

關鍵點總結

擴展變體思考

• Unicode 字符串：boolean[] 不適用，改用 HashSet<Character> 或 Character.toLowerCase 統一判斷
• 自定義元音集合：作為參數傳入，提高復用性
• 流式處理：不可原地修改，需緩衝區或雙端隊列
• 原地修改 char[] 參數：若 API 允許傳入可變數組，可省去複製開銷

面試加分回答

「雙指針左右掃描，boolean[128] 數組 O(1) 判斷元音，遇到則交換並移動指針。時間 O(n)，空間 O(n) (char[] 複製)。注意字符串不可變需轉數組，大小寫全覆蓋，邊界條件 left