059 · Reverse Vowels of a String

algorithm
Published

July 16, 2026

My First Thoughts

嗯，这道题有意思的。

输入只有一个字符串 s，要做的事情其实很直接：

只把元音字符 reverse 一下。

那第一个问题就是：

元音有哪些？

题目里说了，元音包括：

a, e, i, o, u
A, E, I, O, U

第二个问题是：

元音的位置很重要，要怎么保存？

因为题目不是让我们把所有字符都反转，而是只反转元音。也就是说，非元音字符应该还在原来的位置。

比如：

s = "hello"

元音是：

e, o

它们的位置分别是：

1, 4

反转以后，位置 1 应该放 o，位置 4 应该放 e。

所以首先能想到用两个 list：

  • 一个 list 保存元音字符
  • 一个 list 保存这些元音字符的位置

大概就是：

vowels = []
positions = []

for index, char in enumerate(s):
    if char in vowel_set:
        vowels.append(char)
        positions.append(index)

然后再把元音反着放回去：

for i in range(len(vowels)):
    j = len(vowels) - 1 - i
    result[positions[i]] = vowels[j]

这里的 result 可以先写成原字符串的字符列表：

result = list(s)

这样非元音字符天然就已经在原来的位置上了。

我们只需要修改元音所在的位置。

完整写出来就是：

def reverseVowels(s):
    vowel_set = set("aeiouAEIOU")
    vowels = []
    positions = []
    result = list(s)

    for index, char in enumerate(s):
        if char in vowel_set:
            vowels.append(char)
            positions.append(index)

    for i in range(len(vowels)):
        j = len(vowels) - 1 - i
        result[positions[i]] = vowels[j]

    return "".join(result)

这个方法应该可以解出来。

而且它的思路很清楚：

先把要反转的东西和它们的位置记下来，再倒着填回去。

Why That Is Not Enough

上面的思路是正确的。

它的问题不是想错了，而是用到的额外空间有点多。

我们额外保存了：

  • vowels：所有元音字符
  • positions：所有元音的位置
  • result：最终要返回的字符列表

其中 result 基本是需要的，因为 Python 里的字符串不能直接修改。

但 vowels 和 positions 其实可以不存。

为什么？

因为反转元音这件事，本质上是在做：

最左边的元音 <-> 最右边的元音
第二个元音     <-> 倒数第二个元音
...

也就是说，我们不一定要先把所有元音收集起来。

可以一边从左边找元音，一边从右边找元音，找到一对就直接交换。

Final Idea

把字符串先变成字符列表：

chars = list(s)

然后准备两个指针：

left = 0
right = len(chars) - 1

left 从左往右走，负责找左边的下一个元音。

right 从右往左走，负责找右边的下一个元音。

如果 chars[left] 不是元音，就说明它不用参与反转，left 继续往右走：

while left < right and chars[left] not in vowel_set:
    left += 1

如果 chars[right] 不是元音，也不用参与反转，right 继续往左走：

while left < right and chars[right] not in vowel_set:
    right -= 1

当左右两边都停下来时，如果 left < right，说明找到了一对需要交换的元音：

chars[left], chars[right] = chars[right], chars[left]

交换以后，这两个元音已经处理完了，所以两个指针继续向中间移动：

left += 1
right -= 1

Why It Works

题目只要求反转元音，非元音字符保持原位。

所以我们只需要关心元音之间的相对顺序。

假设字符串里的元音从左到右是：

v1, v2, v3, v4

反转以后应该变成：

v4, v3, v2, v1

这正好对应：

v1 和 v4 交换
v2 和 v3 交换

左右双指针做的就是这件事。

left 找到当前最左边还没处理的元音，right 找到当前最右边还没处理的元音，然后交换它们。

非元音字符不会被交换，因为指针遇到非元音时会直接跳过。

当 left >= right 时，说明所有需要成对交换的元音都已经处理完了。

最后把字符列表重新拼成字符串即可。

Code

def reverseVowels(s):
    vowel_set = set("aeiouAEIOU")
    chars = list(s)
    left = 0
    right = len(chars) - 1

    while left < right:
        while left < right and chars[left] not in vowel_set:
            left += 1

        while left < right and chars[right] not in vowel_set:
            right -= 1

        chars[left], chars[right] = chars[right], chars[left]
        left += 1
        right -= 1

    return "".join(chars)

Complexity

Time \(O(n)\) - left 和 right 总共只会扫描整个字符串一次
Space \(O(n)\) - Python 字符串不能原地修改，所以需要 chars 保存字符列表

Takeaway

如果题目要求“只反转某一类字符”，第一反应可以是把这些字符和位置收集起来再倒着填回去。进一步优化时，可以想想这是不是一个“最左边和最右边配对交换”的问题，也就是左右双指针。

← Quiz