LeetCode如何反转字符串中的元音字母

# LeetCode如何反转字符串中的元音字母

## 问题描述

[LeetCode 345题](https://leetcode.com/problems/reverse-vowels-of-a-string/)要求我们编写一个函数，反转字符串中的元音字母。具体规则如下：

- 元音字母包括：a, e, i, o, u（大小写都算）
- 需要保持非元音字母的原始位置
- 只反转元音字母的出现顺序

**示例：**

输入: “hello” 输出: “holle”

输入: “leetcode” 输出: “leotcede”

## 解决思路

### 方法一：双指针法

这是最直观高效的解决方案，时间复杂度O(n)，空间复杂度O(1)。

```python
def reverseVowels(s: str) -> str:
    vowels = {'a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U'}
    s_list = list(s)
    left, right = 0, len(s) - 1
    
    while left < right:
        # 找到左边的元音
        while left < right and s_list[left] not in vowels:
            left += 1
        # 找到右边的元音
        while left < right and s_list[right] not in vowels:
            right -= 1
        
        # 交换元音
        s_list[left], s_list[right] = s_list[right], s_list[left]
        left += 1
        right -= 1
    
    return ''.join(s_list)

方法二：收集反转法

另一种思路是先收集所有元音再反转，适合函数式编程爱好者。

def reverseVowels(s: str) -> str:
    vowels = [c for c in s if c.lower() in {'a','e','i','o','u'}]
    return ''.join(vowels.pop() if c.lower() in {'a','e','i','o','u'} else c for c in s)

代码解析

双指针实现细节

1. 初始化：

   • 将字符串转为列表（Python中字符串不可变）
   • 设置左右指针分别指向首尾

2. 双指针移动：

   • 左指针向右移动直到找到元音
   • 右指针向左移动直到找到元音

3. 交换操作：

   • 当左右指针都找到元音时进行交换
   • 交换后指针继续向中间移动

边界情况处理

• 空字符串：直接返回
• 无元音字符串：原样返回
• 大小写混合：需要识别大小写元音
• 连续元音情况：正常交换

复杂度分析

注：Python中字符串不可变，必须转为列表操作，因此空间复杂度无法优化到O(1)

测试用例验证

test_cases = [
    ("hello", "holle"),
    ("leetcode", "leotcede"),
    ("aA", "Aa"),
    ("xyz", "xyz"),
    ("", ""),
    ("a.b,.", "a.b,."),
    ("aeiou", "uoiea")
]

for input_str, expected in test_cases:
    assert reverseVowels(input_str) == expected

常见错误

1. 遗漏大写元音：

   # 错误实现
   vowels = {'a','e','i','o','u'}  # 漏了大写
   

2. 指针越界：

   while s_list[left] not in vowels:  # 缺少left < right条件
   

3. 字符串不可变：

   s[left] = s[right]  # Python中会报错
   

语言特性应用

Python优化技巧

1. 使用集合查找：

   vowels = {'a','e','i','o','u','A','E','I','O','U'}  # O(1)查找
   

2. 列表推导式：

   [c for c in s if c.lower() in vowels]
   

Java实现对比

public String reverseVowels(String s) {
    Set<Character> vowels = new HashSet<>(
        Arrays.asList('a','e','i','o','u','A','E','I','O','U'));
    char[] chars = s.toCharArray();
    int left = 0, right = s.length() - 1;
    while(left < right) {
        while(left < right && !vowels.contains(chars[left])) left++;
        while(left < right && !vowels.contains(chars[right])) right--;
        char temp = chars[left];
        chars[left++] = chars[right];
        chars[right--] = temp;
    }
    return new String(chars);
}

进阶思考

1. 如何处理Unicode元音？需要包含更多语言的元音字符
2. 元音判断优化：可以用位运算或ASCII值预计算
3. 并行化处理：对于超长字符串可以考虑分段处理

总结

通过这道题目我们学会了： - 双指针法处理字符交换 - 边界条件的全面考虑 - 不同语言的字符串处理差异 - 测试用例的设计方法

建议读者尝试用其他语言实现，并思考如何优化元音判断的效率。 “`