Python字符串元音反转代码优化求助：长串处理超时

原实现代码 #

class Solution:
    def reverseVowels(self, s: str) -> str:
        indexes = []
        consonants = []
        vowels = []
        s2 = ""
        for i in range(len(s)):
            if s[i].lower() in ["a", "e", "i", "o", "u"]:
                indexes.append(i)
                vowels.append(s[i])
            else:
                consonants.append(s[i])
        for j in range(len(s)):
            if j in indexes:
                s2 += vowels[-1]
                del vowels[-1]
            else:
                s2 += consonants[0]
                del consonants[0]
        return s2

原代码的性能瓶颈 #

你认为时间复杂度是O(n)，但实际存在几个关键耗时点：

• j in indexes：每次判断都要遍历列表查找，时间复杂度O(k)（k为元音数量），整体时间复杂度退化为O(n*k)，超长字符串下会大幅变慢。
• del consonants[0]：列表删除头部元素需要移动后续所有元素，单次操作时间复杂度O(m)（m为辅音数量），多次执行后累计耗时极高。
• 字符串拼接s2 += ...：Python字符串是不可变对象，每次拼接都会生成新字符串，时间复杂度O(n²)，超长字符串下效率极低。

优化后的双指针方案 #

用双指针从两端向中间遍历，直接交换元音位置，无需额外存储索引和辅音数组，时间复杂度严格O(n)，空间复杂度O(n)（仅用于将字符串转为可变列表）：

class Solution:
    def reverseVowels(self, s: str) -> str:
        vowels = {'a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U'}
        s_list = list(s)
        left, right = 0, len(s_list) - 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)

优化点说明 #

• 用集合存储元音：集合的查找操作是O(1)，比列表查找效率高得多。
• 双指针单次遍历：一次遍历完成所有元音交换，无需二次遍历字符串。
• 列表存储字符：列表是可变对象，交换操作O(1)，最后用join拼接成字符串，时间复杂度O(n)，远优于多次字符串拼接。
• 无额外冗余存储：不需要单独存储辅音和索引，节省空间的同时避免了删除列表元素的耗时操作。

内容的提问来源于stack exchange，提问作者Viru2008