难度: Easy
给你一个字符串 s ，仅反转字符串中的所有元音字母，并返回结果字符串。
元音字母包括 'a'、'e'、'i'、'o'、'u'，且可能以大小写两种形式出现不止一次。
示例 1：
输入：s = "hello" 输出："holle"
示例 2：
输入：s = "leetcode" 输出："leotcede"
提示：
1 <= s.length <= 3 * 105s由 可打印的 ASCII 字符组成
Submission
运行时间: 30 ms
内存: 16.9 MB
class Solution:
def reverseVowels(self, s: str) -> str:
table = {'a','e','i','o','u','A','E','I','O','U'}
left = 0
right = len(s)-1
ss = list(s)
while left<right:
if ss[left] in table and ss[right] in table:
ss[left], ss[right] = ss[right], ss[left]
left+=1
right-=1
elif ss[left] in table and ss[right] not in table:
right-=1
elif ss[left] not in table and ss[right] in table:
left+=1
else:
left+=1
right-=1
return ''.join(ss)
Explain
本题解使用双指针的方法来解决反转字符串中元音字母的问题。具体思路如下： 1. 定义一个哈希表 table 存储所有元音字母，方便后续判断字符是否为元音字母。 2. 定义双指针 left 和 right，分别指向字符串的开头和结尾。 3. 将字符串转换为列表 ss，方便修改字符。 4. 当 left 小于 right 时，进入循环： - 如果 ss[left] 和 ss[right] 都是元音字母，则交换两个字符，并将 left 右移、right 左移。 - 如果 ss[left] 是元音字母而 ss[right] 不是，则 right 左移。 - 如果 ss[left] 不是元音字母而 ss[right] 是，则 left 右移。 - 如果 ss[left] 和 ss[right] 都不是元音字母，则 left 右移、right 左移。 5. 循环结束后，将列表 ss 重新拼接为字符串并返回结果。
时间复杂度: O(n)
空间复杂度: O(n)
class Solution:
def reverseVowels(self, s: str) -> str:
# 定义哈希表存储元音字母
table = {'a','e','i','o','u','A','E','I','O','U'}
# 定义双指针
left = 0
right = len(s)-1
# 将字符串转换为列表
ss = list(s)
# 当 left 小于 right 时进入循环
while left<right:
# 如果 ss[left] 和 ss[right] 都是元音字母，交换两个字符
if ss[left] in table and ss[right] in table:
ss[left], ss[right] = ss[right], ss[left]
left+=1
right-=1
# 如果 ss[left] 是元音字母而 ss[right] 不是，right 左移
elif ss[left] in table and ss[right] not in table:
right-=1
# 如果 ss[left] 不是元音字母而 ss[right] 是，left 右移
elif ss[left] not in table and ss[right] in table:
left+=1
# 如果 ss[left] 和 ss[right] 都不是元音字母，left 右移、right 左移
else:
left+=1
right-=1
# 将列表重新拼接为字符串并返回结果
return ''.join(ss)
Explore
在Python中，字符串是不可变的数据类型，这意味着一旦创建了字符串，就不能修改其中的单个字符。要进行字符交换，我们需要将字符串转换成可变的数据类型，如列表。在列表中完成所有必要的修改后，可以将列表转换回字符串来得到最终结果。这种方法比创建多个字符串副本更为高效，尤其是在需要多次修改字符串时。
使用哈希表（在Python中实现为集合）来存储和查找元音字母具有更高的效率。在哈希表中，查找操作的平均时间复杂度为O(1)，而在字符串中查找字符的时间复杂度为O(n)，其中n是字符串的长度。这意味着使用哈希表可以更快地判断一个字符是否为元音，特别是在字符集较大或查找操作非常频繁的情况下。
哈希表中同时包含元音字母的大写和小写形式说明算法是大小写不敏感的，即它可以正确识别并处理大写和小写的元音字母。包括两种形式是为了确保算法能够在不区分大小写的情况下工作，反转所有的元音字母，无论它们出现在字符串中的位置或形式如何。
循环条件`left < right`确保了只要左指针位于右指针的左侧，循环就会继续执行。这样的条件通常足以确保所有元音字母都被考虑到，因为算法会从两端向中间遍历字符串。当两个指针相遇时，意味着字符串的所有部分都已经被考虑过，不会遗漏任何元音字母。此外，如果字符串中间的字符是元音，它在指针相遇时也会被检查。因此，这一条件通常不会导致遗漏。