【LC75】No345. 反转字符串中的元音字母

题目描述

给你一个字符串 s ，仅反转字符串中的所有元音字母，并返回结果字符串。

元音字母包括 'a'、'e'、'i'、'o'、'u'，且可能以大小写两种形式出现不止一次。

示例

示例 1：

输入：s = "IceCreAm"
输出："AceCreIm"
解释：s 中的元音是 ['I', 'e', 'e', 'A']。反转这些元音，s 变为 "AceCreIm".

示例 2：

输入：s = "leetcode"
输出："leotcede"

链接

思路

很好理解的题目，没有背景设置，所以中译中环节省略。

需要注意的一点是，别忘了大写字符。

解法一：简单暴力

参照示例 1，我们首先遍历字符 s，获取字符串中的所有元音字符，记录至容器中。

之后再遍历一次字符串 s，遇到元音字符时，取出容器最后放入的字符替换。

依照思路，容器中的字符需要先进后出，因此我们选择栈 Stack 来存储。

代码

class Solution {
    public String reverseVowels(String s) {
        Stack<Character> stack = new Stack<>();
        char[] arr = s.toCharArray();
        // 存储元音字符
        for (int i = 0; i < arr.length; i++) {
            if (isVowel(s.charAt(i))) {
                stack.push(s.charAt(i));
            }
        }
        // 替换字符
        for (int i = 0; i < arr.length; i++) {
            if (isVowel(s.charAt(i))) {
                arr[i] = stack.pop();
            }
        }
        return new String(arr);
    }
    // 判断是否为元音字符
    public boolean isVowel(char ch) {
        return "aeiouAEIOU".indexOf(ch) >= 0;
    }
}

• 时间复杂度：O(n)

• 空间复杂度：O(n)

解法二：双指针

解法一使用了额外的栈来记录字符串 s 中的元音字符，并且使用了两次遍历。

那么我们能否不使用额外的栈，且在一次遍历中处理交换呢？

——包可以的。

看到“遍历”和“交换”，很容易联想到双指针法。

使用两个指针分别指向头和尾。在循环中，遇到非元音字符则继续移动指针，直到遇到两个指针同时指向元音字符，此时直接交换即可。

代码

class Solution {
    public String reverseVowels(String s) {
        char[] arr = s.toCharArray();
        int i = 0, j = arr.length - 1;
        while (i < j) {
            if (!isVowel(arr[i])) {
                i++;
            } else if (!isVowel(arr[j])) {
                j--;
            } else {
                char tmp = arr[i];
                arr[i] = arr[j];
                arr[j] = tmp;
                i++;
                j--;
            }
        }
        return new String(arr);
    }
    // 判断是否为元音字符
    public boolean isVowel(char ch) {
        return "aeiouAEIOU".indexOf(ch) >= 0;
    }
}

• 时间复杂度：O(n)

• 空间复杂度：O(n)