Easy

题目描述

给定一个字符串 s，仅反转字符串中的元音字母并返回。

元音字母包括 'a'、'e'、'i'、'o'、'u'，它们可以以大小写形式出现，且可能出现多次。

示例 1：

输入：s = "IceCreAm"
输出："AceCreIm"
解释：s 中的元音字母为 ['I', 'e', 'e', 'A']。反转这些元音字母后，s 变成 "AceCreIm"。

示例 2：

输入：s = "leetcode"
输出："leotcede"

提示：

  • 1 <= s.length <= 3 * 10^5
  • s 由可打印的 ASCII 字符组成

解题思路

这道题可以使用双指针技巧来解决。核心思想是用两个指针分别从字符串的首尾开始，向中间移动，找到元音字母时进行交换。

解题思路：

  1. 双指针法（推荐）： 设置左右两个指针，分别从字符串开头和结尾开始。左指针向右移动寻找元音字母，右指针向左移动寻找元音字母。当两个指针都找到元音字母时，交换它们的位置，然后继续移动指针，直到两指针相遇。

  2. 先收集再反转： 也可以先遍历一遍字符串收集所有元音字母，将它们反转后再重新放回原位置。但这种方法需要额外的空间存储元音字母。

实现细节：

  • 需要判断字符是否为元音字母，包括大小写
  • 使用集合或字符串查找来快速判断元音字母
  • 注意字符串在某些语言中是不可变的，需要转换为字符数组进行操作

双指针法的时间复杂度为 O(n)，空间复杂度为 O(1)（除了输出所需的空间），是最优解法。

代码实现

class Solution {
public:
    string reverseVowels(string s) {
        string vowels = "aeiouAEIOU";
        int left = 0, right = s.length() - 1;
        
        while (left < right) {
            while (left < right && vowels.find(s[left]) == string::npos) {
                left++;
            }
            while (left < right && vowels.find(s[right]) == string::npos) {
                right--;
            }
            if (left < right) {
                swap(s[left], s[right]);
                left++;
                right--;
            }
        }
        
        return s;
    }
};

class Solution:
    def reverseVowels(self, s: str) -> str:
        vowels = set('aeiouAEIOU')
        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
            if left < right:
                s_list[left], s_list[right] = s_list[right], s_list[left]
                left += 1
                right -= 1
        
        return ''.join(s_list)

public class Solution {
    public string ReverseVowels(string s) {
        HashSet<char> vowels = new HashSet<char> {'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--;
            }
            if (left < right) {
                char temp = chars[left];
                chars[left] = chars[right];
                chars[right] = temp;
                left++;
                right--;
            }
        }
        
        return new string(chars);
    }
}

var reverseVowels = function(s) {
    const vowels = new Set(['a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U']);
    const chars = s.split('');
    let left = 0, right = s.length - 1;
    
    while (left < right) {
        while (left < right && !vowels.has(chars[left])) {
            left++;
        }
        while (left < right && !vowels.has(chars[right])) {
            right--;
        }
        if (left < right) {
            [chars[left], chars[right]] = [chars[right], chars[left]];
            left++;
            right--;
        }
    }
    
    return chars.join('');
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)需要遍历字符串一次，每个字符最多被访问一次
空间复杂度O(1)只使用常数额外空间（不包括输出字符串所需空间）

相关题目