Reverse Vowels of a String

345. 反转字符串中的元音字母

分析

定义元音集合：
- 使用一个哈希集合存储所有的元音字母，用于快速判断一个字符是否是元音
双指针法：
- 初始化两个指针：i 指向字符串的起始位置，j 指向字符串的末尾位置
- 使用双指针从两端向中间遍历，找到最近的两个元音字母，交换它们的位置
具体步骤：
- 如果 s[i] 不是元音，则 i 向右移动
- 如果 s[j] 不是元音，则 j 向左移动
- 当 s[i] 和 s[j] 都是元音时，交换它们，并同时移动两个指针
- 重复上述过程，直到两个指针相遇或交错

时间复杂度

双指针最多遍历字符串一次，每次操作的时间为 O(1)

总时间复杂度 O(n)

空间复杂度

空间复杂度为 O(1)

C++代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26


class Solution {
public:
    string reverseVowels(string s)
    {
        // 定义元音字母集合
        std::unordered_set<char> hash = {
            'a', 'e', 'i', 'o', 'u',
            'A', 'E', 'I', 'O', 'U'
        };

        // 双指针初始化
        for (int i = 0, j = s.size() - 1; i < j; ++i, --j)
        {
            // 左指针寻找元音
            while (i < j && !hash.count(s[i]))
                ++i;
            // 右指针寻找元音
            while (i < j && !hash.count(s[j]))
                --j;
            // 交换两个元音字母
            std::swap(s[i], s[j]);
        }

        return s; // 返回结果字符串
    }
};