【LeetCode每日一题】LeetCode 345.反转字符串中的元音字母

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

题目描述

给定一个字符串 s，你需要反转字符串中所有的元音字母，并返回新的字符串。
元音字母是 a, e, i, o, u，这些字母的大小写都会被考虑。

示例 1:
输入: s = "hello"
输出: "holle"

示例 2:
输入: s = "leetcode"
输出: "leotcede"

Java 实现代码

class Solution {
    public String reverseVowels(String s) {
        // 用一个字符数组来保存字符串，便于修改
        char[] arr = s.toCharArray();
        // 设置左右指针
        int left = 0, right = arr.length - 1;
        
        // 使用双指针反转元音字母
        while (left < right) {
            // 找到左边的元音字母
            while (left < right && !isVowel(arr[left])) {
                left++;
            }
            // 找到右边的元音字母
            while (left < right && !isVowel(arr[right])) {
                right--;
            }
            // 交换元音字母
            char temp = arr[left];
            arr[left] = arr[right];
            arr[right] = temp;
            left++;
            right--;
        }
        
        // 返回新的字符串
        return new String(arr);
    }
    // 判断字符是否为元音字母
    private boolean isVowel(char c) {
        return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u' || c == 'A' || c == 'E' || c == 'I' || c == 'O'
                || c == 'U';
    }
}

解题思路

1. 双指针法: 使用两个指针 left 和 right 分别指向字符串的两端。左指针向右移动，右指针向左移动，直到它们相遇。
2. 判断元音字母: 定义一个辅助方法 isVowel() 来判断一个字符是否是元音字母。可以通过字符比较的方式判断是否属于 a, e, i, o, u 或其大写形式。
3. 交换元音字母: 每当找到左右指针指向的字符都是元音字母时，交换这两个字符。
4. 跳过非元音字母: 如果某个指针指向的字符不是元音字母，则该指针继续向中间移动，直到找到下一个元音字母。
5. 终止条件: 当左指针和右指针相遇或交错时，停止交换。

时间复杂度分析

• 时间复杂度: O(n)，其中 n 是字符串的长度。我们遍历字符串一次，每次操作的时间是常数时间。
• 空间复杂度: O(n)，我们将字符串转换为字符数组进行操作。