344. Reverse String

發表於 | 分類於

problem

solution

1
2
3
4
5
6
class Solution {
public:
    void reverseString(vector<char>& s) {
        reverse(s.begin(), s.end());
    }
};

option 1 - Two Pointers

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    void swap(char *a, char* b){
        *a = *a^*b;
        *b = *a^*b;
        *a = *a^*b;
    }
    void reverseString(vector<char>& s) {
        int l =0, r=s.size()-1;
        while(l<r) swap(&s[l++], &s[r--]);
    }
};

option 2 - stack

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    void reverseString(vector<char>& s) {
        stack<char> sta;
        for(auto c:s) sta.push(c);
        for(auto &c :s){
            c = sta.top();
            sta.pop();
        }
    }
};

option 3 - without loop , using recursive

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    void reverseString(vector<char>& s) {
        if(s.size() != 1){
        char temp = s[0];
        s.erase(s.begin());
        reverseString(s);
        s.push_back(temp);
       }
    }
};

analysis

  • option 1 - Two Pointers
    • time complexity O(n)
    • space complexity O(1)
  • option 2 - stack
    • time complexity O(n)
    • space complexity O(n)