頭尾顛倒 反轉字串 Reverse String_Leetcode #344

Liam Shaw on Unsplash

題目敘述 Reverse String

給定一個輸入字串陣列，要求我們反轉整個字串陣列，並且必須是in-place原位操作，只能使用O(1)常數空間的演算法來完成。

測試範例

Input: s = ["h","e","l","l","o"]
Output: ["o","l","l","e","h"]

Example 2:

Input: s = ["H","a","n","n","a","h"]
Output: ["h","a","n","n","a","H"]

約束條件

Constraints:

• 1 <= s.length <= 10^5

輸入字串陣列長度介於1~十萬之間。

• s[i] is a printable ascii character.

每個陣列元素都是可列印的ASCII字元

觀察

反轉整個字元，相當於順序顛倒，頭尾對調。

例如: hello <-> olleh

示意圖

演算法 雙指針 Two pointers

建立左、右兩個指針，初始化呈第一個索引和最後一個索引。

每回合對調左右兩個指針對應到的字元，並且逐漸往中心靠攏，由外而內進行反轉。

程式碼 雙指針 Two pointers

class Solution:
    def reverseString(self, s: List[str]) -> None:            
        
	    ​		# one points to head position, the other points to tail position
        left, right = 0, len(s)-1
        
   ​		 		# reverse string by two pointers
        while left < right:
            
            s[left], s[right] = s[right], s[left]
            
            left,right = left+1, right-1

複雜度分析

時間複雜度: O(n)

最多只需要O(n/2)次對調，即可完成整個字串陣列的反轉。

空間複雜度: O(1)

使用的都是固定尺寸的臨時變數，所需空間為O(1)常數級別。

Reference:

[1] Reverse String - LeetCode