Leetcode-345-反转字符串中的元音字母

Leecode-345-反转字符串中的元音字母

思路：双指针

题目描述：

将元音字母进行交换

Given s = "leetcode", return "leotcede".

Solution：双指针

• 本题为基础双指针法交换前后元音元素；

• 一般遇见字符串问题，能转成字符数组就尽量转(方便)；

• 转换成数组后，分别定义前后两个索引指针用 while 依次遍历数组；

• 定义 isVowel() 方法将非元音元素返回给判断处，然后移动指针直到符合元音的位置，然后 tmp 进行交换即可；

• 最后扫描完数组后，一定要在返回的时候再转成字符串 String 输出。

Java

Solution :

class Solution {
    public String reverseVowels(String s) {
        // 先将字符串转换成字符数组（方便操作）
        // 以上只是针对Java语言来说 因为charAt(i) 每次都要检查是否越界 有性能的消耗
        char[] arr = s.toCharArray();
    
        // 双指针
        int n = arr.length;
        int left = 0;
        int right= n - 1;

        // 循环交换
        while(left < right){
            // 从左边判断当前元素是否是元音
            while(left < n && !isVowel(arr[left])){
                left++;
            }

            // 从右边判断当前元素是否是元音
            while(right > 0 && !isVowel(arr[right])){
                right--;
            }

            // 如果没有元音的话
            if(left >= right){
                break;
            }

            // 有的话交换前后的元音字符
            swap(arr,left,right);


            // 指针后移
            left++;
            right--;
        }

        // 最后转换回字符串进行输出
        return new String(arr);
    }

    // 交换函数
    private void swap(char[] arr, int a ,int b){
        char temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }

    // 判断是否是元音字符
    private boolean isVowel(char ch){
        // 这里直接用return 语句返回，不要返回true 或者 false
        return ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u'
                || ch == 'A' || ch == 'E' || ch == 'I' || ch == 'O' || ch == 'U';
    }
}

复杂度分析

• 时间复杂度：O(N)只需要遍历所有元素一次
• 空间复杂度：O(1)只需要使用两个额外的变量

Python

Solution :

class Solution:
    def reverseVowels(self, s: str) -> str:
        vowels = ['a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U']
        string = list(s)
        i,j = 0,len(s) - 1
        while i <= j:
            if s[i] not in vowels:
                i += 1
            elif s[j] not in vowels:
                j -= 1
            else:
                string[i],string[j]= string[j],string[i]
                i += 1
                j -= 1
        return ''.join(string)

打赏