【LeetCode】344. Reverse String

Link

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 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]);
        }
    }
};
Select a repo