0345. Reverse Vowels of a String
================================
题目信息
--------
:题号: 0345
:难度: Easy
:主题: 字符串、元音位置、大小写、局部反转
:原题: `LeetCode 0345 `_
:重点: 元音包含大小写 a/e/i/o/u、只反转元音出现顺序、所有非元音字符位置保持不变
题目重述
--------
给定字符串 ``s``,找出其中所有元音字符,并把这些元音按照出现顺序整体反转后放回原来的元音位置;其他字符必须继续留在原下标。元音包括小写和大写的 ``a``、``e``、``i``、``o``、``u``。
``s`` 的长度位于 ``[1, 3 * 10^5]``,由可打印 ASCII 字符组成,因此可能包含字母、数字、空格和标点。相同元音可以出现多次;若字符串中少于两个元音,返回值与输入相同。
自建示例
--------
同时包含大小写元音和标点:
.. code-block:: text
输入:s = "aA-bE"
输出:"EA-ba"
解释:元音序列为 a、A、E,反转后为 E、A、a;连字符和字母 b 的位置保持不变。
没有元音:
.. code-block:: text
输入:s = "rhythm"
输出:"rhythm"
解释:没有字符需要交换,因此字符串保持原样。
只让两个指针停在元音上
------------------------
维护字符串两端的 ``left``、``right``。左指针跳过非元音,右指针从右向左跳过非元音;当两者都停在元音上时交换,再同时向内移动。非元音从未参与交换,因此其下标位置保持不变,而元音序列被从两端逐对反转。
判断元音时同时接受大小写五种元音,不能只按小写字符判断;两个指针相遇后,所有元音位置都已处理。
C++ 实现
--------
.. code-block:: cpp
class Solution {
bool isVowel(char c) {
return std::string("aeiouAEIOU").find(c)
!= std::string::npos;
}
public:
std::string reverseVowels(std::string s) {
int left = 0;
int right = static_cast(s.size()) - 1;
while (left < right) {
while (left < right && !isVowel(s[left])) ++left;
while (left < right && !isVowel(s[right])) --right;
if (left < right) {
std::swap(s[left++], s[right--]);
}
}
return s;
}
};
代码分析
--------
每个指针只向内移动,非元音只被检查而不被改写;交换次数等于元音位置数量的一半。使用固定长度的元音集合判断仍是常数成本,时间复杂度为 ``O(n)``,额外空间为 ``O(1)``(不计返回字符串)。