如何优化LeetCode 345题Python代码的时间复杂度？

题目任务 #

给定一个字符串s，仅反转字符串中的所有元音字母并返回结果。元音字母包括a、e、i、o、u，且区分大小写，可出现多次。

示例1 #

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

现有代码 #

class Solution:
    def reverseVowels(self, s: str) -> str:
        vowels = ['a', 'A', 'e', 'E', 'i', 'I', 'O', 'o', 'U','u']
        found = []
        location = []
        for i in range(len(s)):
            if s[i] in vowels:
                found.append(s[i])
                location.append(i)
        location.reverse()
        r2 = []
        for i in range(len(s)):
            if i in location:
                r2.append(found[location.index(i)])
            else: r2.append(s[i])
        s = ''.join(r2)
        return(s)

问题 #

这段代码通过了479/480个测试用例，但最后一个超大规模测试用例超时。

优化方案 #

问题根源 #

你的代码超时核心是两个高耗时操作：

1. i in location：location是列表，判断元素存在的时间复杂度为O(n)，大规模字符串下重复执行会累积极高耗时。
2. location.index(i)：同样是列表查找操作，时间复杂度O(n)，进一步放大了耗时。
   另外，vowels用列表存储，判断字符是否为元音的时间是O(10)，换成集合可降到O(1)，虽影响较小但也是优化点。

最优解法：双指针法 #

针对这个问题，最高效的解法是双指针法，无需额外存储所有元音位置，直接在字符数组上交换元音，时间复杂度O(n)，空间复杂度O(n)（因Python字符串不可变，需转数组操作）：

class Solution:
    def reverseVowels(self, s: str) -> str:
        vowels = {'a', 'A', 'e', 'E', 'i', 'I', 'o', 'O', 'u', '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
            # 交换找到的一对元音
            s_list[left], s_list[right] = s_list[right], s_list[left]
            left += 1
            right -= 1
        
        return ''.join(s_list)

优化点说明 #

1. 集合存储元音：将vowels改为集合，判断字符是否为元音的时间从O(10)降至O(1)。
2. 双指针遍历：
   • 左右指针分别从两端向中间遍历，找到元音就交换，全程仅遍历字符串一次。
   • 避免了原代码中存储所有元音位置、反复查找的高开销操作。
3. 字符串转数组：Python字符串不可变，转成列表后可直接修改元素，避免频繁拼接字符串的额外消耗。

基于原思路的小修改 #

如果不想更换双指针逻辑，可通过将location列表改为字典，消除列表查找的O(n)操作，把时间复杂度从O(n²)降到O(n)：

class Solution:
    def reverseVowels(self, s: str) -> str:
        vowels = {'a', 'A', 'e', 'E', 'i', 'I', 'o', 'O', 'u', 'U'}
        found = []
        pos_map = {}
        for idx, char in enumerate(s):
            if char in vowels:
                found.append(char)
                pos_map[idx] = len(found) - 1  # 记录当前位置对应的原元音索引
        
        found.reverse()
        s_list = list(s)
        for pos, original_idx in pos_map.items():
            s_list[pos] = found[original_idx]
        
        return ''.join(s_list)

内容的提问来源于stack exchange，提问作者D.S.Dudhia