What is the two-pointer approach in the Reverse Vowels of a String problem?

The two-pointer approach uses one pointer starting from the beginning of the string and another from the end. These pointers move towards each other, swapping vowels until they cross.

How do you handle vowels in both lowercase and uppercase?

You treat both lowercase and uppercase vowels ('a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U') as valid vowels, ensuring the case is respected during swapping.

Can I use extra space in the Reverse Vowels of a String problem?

While the problem can be solved in-place with O(1) space, using extra space for easier string manipulation is acceptable, especially for readability, which would increase space complexity to O(n).

Why is the two-pointer approach efficient for this problem?

The two-pointer approach is efficient because it scans the string in linear time, only swapping vowels while leaving consonants untouched. This reduces the time complexity to O(n).

How can GhostInterview help with Reverse Vowels of a String?

GhostInterview provides insights into optimizing both time and space complexity while practicing key techniques such as two-pointer scanning, ensuring a thorough solution.

#345

Easy

auto_awesome双·指针·invariant

LeetCode 题解工作台

反转字符串中的元音字母

给你一个字符串 s ，仅反转字符串中的所有元音字母，并返回结果字符串。元音字母包括 'a' 、 'e' 、 'i' 、 'o' 、 'u' ，且可能以大小写两种形式出现不止一次。示例 1：输入： s = "IceCreAm" 输出： "AceCreIm" 解释： s 中的元音是 ['I', '…

双指针字符串

题目描述

给你一个字符串 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⁵
s 由 可打印的 ASCII 字符组成

lightbulb

解题思路

方法一：双指针

我们可以用两个指针 $i$ 和 $j$ ，初始时分别指向字符串的首尾。

每次循环判断 $i$ 指向的字符是否是元音字母，如果不是则向后移动 $i$ ；同理，判断 $j$ 指向的字符是否是元音字母，如果不是则向前移动 $j$ 。如果此时 $i \lt j$ ，那么 $i$ 和 $j$ 指向的字符都是元音字母，交换这两个字符。然后向后移动 $i$ ，向前移动 $j$ 。继续上述操作，直到 $i \ge j$ 。

时间复杂度 $O(n)$ ，其中 $n$ 是字符串的长度。空间复杂度 $O(|\Sigma|)$ ，其中 $\Sigma$ 是字符集的大小。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

class Solution:
    def reverseVowels(self, s: str) -> str:
        vowels = "aeiouAEIOU"
        i, j = 0, len(s) - 1
        cs = list(s)
        while i < j:
            while i < j and cs[i] not in vowels:
                i += 1
            while i < j and cs[j] not in vowels:
                j -= 1
            if i < j:
                cs[i], cs[j] = cs[j], cs[i]
                i, j = i + 1, j - 1
        return "".join(cs)

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Look for proficiency with the two-pointer technique and how candidates manage pointer movement.
question_mark
Ensure the candidate accounts for both uppercase and lowercase vowels during swaps.
question_mark
Assess the candidate's ability to optimize for space complexity, especially when handling large input sizes.

warning

常见陷阱

外企场景

error
Failing to skip non-vowel characters efficiently can lead to unnecessary checks and inefficiency.
error
Not handling both uppercase and lowercase vowels correctly might result in incorrect outputs.
error
Attempting to reverse vowels without properly converting the string to a mutable data structure could cause errors in languages where strings are immutable.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Reverse the vowels only in a substring, not the entire string.
arrow_right_alt
Add a limit to the number of vowels that can be reversed, such as reversing only the first 3 vowels.
arrow_right_alt
Consider a case where only specific vowels (e.g., 'a' and 'o') are reversed, not all vowels.

help

常见问题

外企场景

继续练习

#344 反转字符串 #392 判断子序列 #443 压缩字符串