LeetCode题解-345.reverse-vowels-of-a-string

345.reverse-vowels-of-a-string

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

示例 1:

输入: "hello"
输出: "holle"

示例 2:

输入: "leetcode"
输出: "leotcede"

说明:
元音字母不包含字母"y"。

题解
本题依然可以通过双指针的方法来求解，问题在于修改字符串比较麻烦，因此，在程序中建立一个新的字符数组来保存翻转后的结果。

class Solution {
    
    // 判断是否为元音字母
    private boolean isVowels(char ch) {
        if(Character.toLowerCase(ch) == 'a' || Character.toLowerCase(ch) == 'e' || Character.toLowerCase(ch) == 'i' || Character.toLowerCase(ch) == 'o' || Character.toLowerCase(ch) == 'u') {
            return true;
        }
        return false;
    }
    
    public String reverseVowels(String s) {
        // 用字符数组res保存最终结果
        char[] res = new char[s.length()];
        // 使用双指针来遍历整个数组
        int i = 0;
        int j = s.length() - 1;
        if(j < 0) {
            return s;
        }
        while(i <= j) {
            if(i == j) {
                res[i] = s.charAt(i);
                return new String(res);
            }
            if(!isVowels(s.charAt(i))) {
                res[i] = s.charAt(i);
                i++;
            } else if(!isVowels(s.charAt(j))) {
                res[j] = s.charAt(j);
                j--;
            } else {
                res[i] = s.charAt(j);
                res[j] = s.charAt(i);
                i++;
                j--;
            }
        }
        return new String(res);
    }
}

在上面的算法中依然是遍历一遍，因此时间复杂度为O(n)，由于新开辟了一个数组空间，空间复杂度也为O(n).