LeetCode算法题(Go语言实现)_05

题目

给你一个字符串 s ，仅反转字符串中的所有元音字母，并返回结果字符串。
元音字母包括 ‘a’、‘e’、‘i’、‘o’、‘u’，且可能以大小写两种形式出现不止一次。

一、Go 语言实现

func reverseVowels(s string) string {
    runes := []rune(s)
    vowels := map[rune]bool{'a': true, 'e': true, 'i': true, 'o': true, 'u': true, 'A': true, 'E': true, 'I': true, 'O': true, 'U': true}
    left, right := 0, len(runes)-1
    
    for left < right {
        // 找到左侧的元音
        for left < right && !vowels[runes[left]] {
            left++
        }
        // 找到右侧的元音
        for left < right && !vowels[runes[right]] {
            right--
        }
        // 交换并移动指针
        if left < right {
            runes[left], runes[right] = runes[right], runes[left]
            left++
            right--
        }
    }
    return string(runes)
}

二、 算法分析

1. 核心思路

• 双指针法：使用左右指针从两端向中间扫描，分别找到元音字母后交换。
• 元音集合：通过哈希集合快速判断字符是否为元音（包含大小写）。

2. 关键步骤

1. 转换字符串为可修改类型：Go 中需将 string 转为 []rune。
2. 初始化双指针：left 从左侧开始，right 从右侧开始。
3. 查找元音并交换：
   • 移动 left 直到指向元音。
   • 移动 right 直到指向元音。
   • 若 left < right，交换这两个位置的字符，并继续向中间移动。
4. 返回结果：将 []rune 转回 string。

3. 复杂度

• 时间复杂度：O(n)，每个字符最多被访问两次（左右指针各一次）。
• 空间复杂度：O(n)，存储 []rune 需要额外空间（Go 中字符串不可变）。

三、图解

四、 边界条件与扩展

1. 无元音字符：直接返回原字符串。
2. 全为元音：如 "aeiou" 反转为 "uoiea"。
3. 大小写混合：如 "aA" 交换为 "Aa"。
4. 单字符或无字符：直接返回原字符串。

五、 总结

• 核心逻辑：双指针法高效定位元音并交换，确保时间复杂度为 O(n)。
• 大小写处理：通过哈希集合统一判断大小写元音。
• 适用场景：类似“对称交换”或“特定元素重排”问题可参考此思路。