# 【LeetCode】344. Reverse String

## Question link
[Link](https://leetcode.com/problems/reverse-string/description/)

## Intuition
> Write a function that reverses a string. The input string is given as an array of characters `s`. You must do this by modifying the input array [in-place](https://en.wikipedia.org/wiki/In-place_algorithm) with `O(1)` extra memory.
給定字串`s`，將其翻轉

最直接想法就是直接使用新的一個字串，並從尾到頭歷遍字串，但是需要`O(n)`的空間，因此如果使用雙指標法的話就不需要這麼多空間，直接交換頭尾兩個指標的字元就好

## Approach
1. 循環整個字串，使用兩個索引來分別索引頭尾元素`i`和`j`，直到`i == j`
1. 交換兩個位置的元素`s[i]`與`s[j]`
2. 將頭尾索引更新，`i++`與`j--`

## Complexity
- Time complexity: $O(n)$
雖然使用雙指標法，但每個元素都還是被操作一次，因此時間複雜度還是`O(n)`
- Space complexity: $O(1)$
空間複雜度為常數，只需要一個 `char` 來暫存交換的字元

## Code

void reverseString(char* s, int sSize) {
    for (int i = 0, j = sSize - 1; i < j; i++, j--){
        char temp = s[i];
        s[i] = s[j];
        s[j] = temp;
    }
}

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

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