題目鏈結：https://leetcode.com/problems/reverse-string/

題目概要

使用原地演算法(in-place algorithm)將題目給定的字串s進行倒轉(reverse) 。

  • 原地演算法(in-place algorithm)：不藉助額外的資料結構就能對輸入的資料進行變換的演算法。（分配少量空間給部分輔助變數是允許的。）
  • 舉例：s = [“H”,“a”,“n”,“n”,“a”,“h”]；倒轉後即 [“h”,“a”,“n”,“n”,“a”,“H”]。

解題思路

  • 利用兩個指標(左右指標i,j)逐漸由左右兩側往中間接近，每次移動一個單位，移動前置換彼此。
  • 當兩指標在中央相會時即完成所有置換的動作。

參考程式碼

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    void reverseString(vector<char>& s) {
        int i=0,j=s.size()-1;
        while(i<j) {
            char temp=s[i];
            s[i]=s[j];
            s[j]=temp;
            i++; j--;
        }
    }
};
  • Using Two Pointers
1
2
3
4
5
6
7
class Solution:
    def reverseString(self, s: List[str]) -> None:
        l,r=0,len(s)-1
        while l<r:
            s[l],s[r]=s[r],s[l]
            l+=1
            r-=1
  • Using Function
1
2
3
class Solution:
    def reverseString(self, s: List[str]) -> None:
        s.reverse()