题目描述

给定一个字符串，请翻转它的所有元音字母。

注意： 元音字母不包含"y"。

样例1

给定 s = "hello", 返回 "holle".

样例2

给定 s = "leetcode", 返回 "leotcede".

算法

(双指针扫描，字符串处理) $O(n)$

用两个指针分别从首尾开始往中间扫描，扫描过程中忽略所有不是元音的字母，然后交换两个指针指向的字符。
扫描过程一直持续到两个指针相遇为止。

时间复杂度分析：字符串中每个元素只被扫描一遍，所以时间复杂度是 $O(n)$。

C++ 代码

class Solution {
public:
    string reverseVowels(string s) {
        char vowels[] = {'a', 'e', 'i', 'o', 'u'};
        unordered_set<char> S;
        for (char c : vowels)
        {
            S.insert(c);
            S.insert(c - 32);
        }
        for (int i = 0, j = s.size() - 1; i < j;)
        {
            while (i < j && !S.count(s[i])) i ++ ;
            while (i < j && !S.count(s[j])) j -- ;
            if (i < j) swap(s[i], s[j]);
            i ++, j -- ;
        }
        return s;
    }
};