LeetCode #345 反轉字元串中的元音字母 雙指針

LeetCode #345 反轉字元串中的元音字母

題目描述

編寫一個函數，以字元串作為輸入，反轉該字元串中的元音字母。

示例 1:

輸入: "hello"
輸出: "holle"
           

示例 2:

輸入: "leetcode"
輸出: "leotcede"
           

說明:

元音字母不包含字母"y"。

思路分析

使用雙指針，雙向收縮，當兩個指針都周遊到元音字元的時候交換。為了快速判斷一個字元是不是元音字元，使用 set 以 O ( 1 ) O(1) O(1) 的時間複雜度搜尋

class Solution:
    def reverseVowels(self, s: str) -> str:
        if not s: return ''
        vowels = {'a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U'}

        i = 0; j = len(s)-1
        result = ['']*len(s)
        while(i <= j):
            ci = s[i]
            cj = s[j]
            if not ci in vowels:
                result[i] = ci
                i += 1
            elif not cj in vowels:
                result[j] = cj
                j -= 1
            else:
                result[i], result[j] = cj, ci
                i += 1
                j -= 1

        return ''.join(result)
           

時間複雜度： O ( N ) O(N) O(N)

空間複雜度： O ( 1 ) O(1) O(1)