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

原题链接

题目描述

编写一个函数，以字符串作为输入，反转该字符串中的元音字母。

提示：元音字母不包含字母 “y” 。

样例

输入样例1：

"hello"

输出样例1：

"holle"

输入样例2：

"leetcode"

输出样例2：

"leotcede"

思路

双指针扫描。

用两个指针，从首尾往中间扫描，扫描过程中跳过非元音字母，然后交换两个指针指向的字符。直到两个指针相遇为止。

时间复杂度：每个字符只会被扫描一遍。时间复杂度是 $O(n)$ 。

代码

C++

class Solution {
public:
    string words = "aeiouAEIOU";

    string reverseVowels(string s) {
        for ( int i = 0, j = s.size() - 1; i < j; i++, j-- )
        {
            while ( i < j && words.find(s[i]) == -1 ) i++;
            while ( i < j && words.find(s[j]) == -1 ) j--;
            swap(s[i], s[j]);
        }
        return s;
    }
};

Java

class Solution {
    String words = "aeiouAEIOU";

    public String reverseVowels(String s) {
        char chs[] = s.toCharArray();
        for ( int i = 0, j = s.length() - 1; i < j; i++, j-- )
        {
            while ( i < j && words.indexOf(chs[i]) == -1 ) i++;
            while ( i < j && words.indexOf(chs[j]) == -1 ) j--;
            char t = chs[i];
            chs[i] = chs[j];
            chs[j] = t;
        }
        return new String(chs);
    }
}