反轉字串中的母音 Reverse Vowels of a String_Leetcode 精選75題解析

Clarissa Watson on Unsplash

題目敘述

題目會給定我們一個字串s，要求我們反轉字串s中所有母音字元的順序，並且以字串的形式輸出。

註: 母音字元為a, e, i, o, u 或者 A, E, I, O, U

題目的原文敘述

測試範例

Example 1:

Input: s = "hello"
Output: "holle"

Example 2:

Input: s = "leetcode"
Output: "leotcede"

約束條件

Constraints:

• 1 <= s.length <= 3 * 10^5
• s consist of printable ASCII characters.

演算法

這一題基本想法滿直覺的，就是用雙指針，一個從左邊往右掃，一個從右邊往左邊掃。每當遇到母音時，就互換位置，反覆迭代，最後雙指針交會時，反轉程序就完成了。

唯一一個實作上要注意的細節是，python string 不像c++ string那樣可以直接透過s[i]去修改，在python 裡面，所有字串都是immutable 不可變的。

因此，我們必須先把字串轉成字元陣列的形式，接著反轉母音順序，最後再輸出為字串，作為最後的答案。

Python 官方文件對於string的說明

程式碼

class Solution:
    def reverseVowels(self, s: str) -> str:
        
        vowel = {'a', 'e', 'i', 'o', 'u','A', 'E', 'I', 'O', 'U'}
        
        new_s = list(s)                 # use python list as buffer for element swap
        last_index = len(s)-1
        left, right = 0, last_index     # initialization for two pointers
        
        while left <= right:
            
            while left <= right and s[left] not in vowel: left +=1
            while left <= right and s[right] not in vowel: right -=1
            
            if left > right:
                break
            
							# swap vowel
            new_s[ left ], new_s[ right ] = new_s[ right ], new_s[ left ]
            
            left, right = left+1, right-1
            
        return ''.join(new_s)

複雜度分析

時間複雜度:O(n)

時間成本落在while loop迭代，線性掃描，頭尾雙指針往中間逼近，所需時間為O(n)

空間複雜度:O(n)

會需要建立額外的暫存空間new_s，來存放字元陣列，所需空間為O(n)