🔗 🟢 344. Reverse String

tags: `雙指標(Two Pointers)`

題意

給定一個字元陣列 $s$ ，實現一個反轉字串的函式。

必須以 $O(1)$ 的額外空間，直接在原地(in-place) 修改輸入陣列。

思路：雙指標(Two Pointers)

寫法一：直接計算對應位置

對於每個位置 $i$ ，我們可以直接計算其對應的位置 $j = n - 1 - i$ ，並交換 $s[i]$ 和 $s[j]$ ，其中 $n$ 為陣列長度。

再來考慮 $i$ 應該遍歷的範圍，由於我們是要將 $s[i]$ 和 $s[j]$ 交換，因此 $i$ 只需要遍歷到 $n / 2 - 1$ 即可。

對於長度 $n$ 為奇數的陣列，中間的元素不需要交換，因此枚舉到 $n / 2 - 1$ 即可。
對於長度 $n$ 為偶數的陣列，最後一次交換發生在 $(i, j) = (n / 2 - 1, n / 2)$ ，因此同樣也是枚舉到 $n / 2 - 1$ 即可。

複雜度分析

時間複雜度： $O(n)$
空間複雜度： $O(1)$

class Solution:
    def reverseString(self, s: List[str]) -> None:
        """
        Do not return anything, modify s in-place instead.
        """
        n = len(s)
        for i in range(n//2):
            s[i], s[n-i-1] = s[n-i-1], s[i]

class Solution {
public:
    void reverseString(vector<char>& s) {
        int n = s.size();
        for (int i = 0; i < n / 2; i++) swap(s[i], s[n - i - 1]);
    }
};

寫法二：相向雙指標

上述方法中需要計算對應位置，並且需要稍微思考一下枚舉的範圍。另一種方法是使用兩個指標 $i$ 和 $j$ ，分別指向陣列的頭尾，然後同時向中間移動，交換 $s[i]$ 和 $s[j]$ ，直到 $i \geq j$ 為止。或是換句話說，當 $i < j$ 時，我們不斷交換 $s[i]$ 和 $s[j]$ ，並同時將 $i$ 加一， $j$ 減一。

複雜度分析

時間複雜度： $O(n)$
空間複雜度： $O(1)$

class Solution:
    def reverseString(self, s: List[str]) -> None:
        """
        Do not return anything, modify s in-place instead.
        """
        i, j = 0, len(s)-1
        while i < j:
            s[i], s[j] = s[j], s[i]
            i += 1
            j -= 1

class Solution {
public:
    void reverseString(vector<char>& s) {
        int i = 0, j = s.size() - 1;
        while (i < j) swap(s[i++], s[j--]);
    }
};