Home | Projects | Notes > Problem Solving > LC - E - 344. Reverse String

LC - E - 344. Reverse String

Solutions in C++

Solution 1

Even if s forms a string it is essentially a vector. The container vector does not provide the function length(). Make sure to use size().

String class also provides the size() member function. (Maybe a good idea to use size() all throughout to minimize confusion.)

Complexity Analysis:

• $T=O(n)$$T = O(n)$

• $S=O(1)$$S = O(1)$

Solution:

xxxxxxxxxx
10
1
class Solution {
2
public:
3
    void reverseString(vector<char>& s) {
4
        unsigned int len = s.size();
5

6
        for (int i = 0; i < len/2; i++) {
7
            swap(s[i], s[len-1-i]);
8
        }
9
    }
10
};

Solution 2

This solution uses beg and end index variables.

Complexity Analysis:

• $T=O(n)$$T = O(n)$

• $S=O(1)$$S = O(1)$

Solution:

xxxxxxxxxx
8
1
class Solution {
2
public:
3
    void reverseString(vector<char>& s) {
4
        for (int beg = 0, end = s.size() - 1; beg < end; ++beg, --end) {
5
            swap(s[beg], s[end]);
6
        }
7
    }
8
};

Solution 3

This solution uses C++ STL stack container to reverse a string. Note that this solution does not satisfy the condition "you must do this by modifying the input array in-place with O(1) extra memory".

Complexity Analysis:

• $T=O(n)$$T = O(n)$

• $S=O(n)$$S = O(n)$

Solution:

xxxxxxxxxx
16
1
class Solution {
2
public:
3
    void reverseString(vector<char>& s) {
4
        stack<char> st;
5

6
        // push the characters into the stack
7
        for (auto pos = s.cbegin(); pos != s.cend(); ++pos)
8
            st.push(*pos);
9

10
        // pop the characters from the stack and insert them back into the string
11
        for (auto pos = s.begin(); pos != s.end(); ++pos) {
12
            *pos = st.top();
13
            st.pop();
14
        }
15
    }
16
};

Solution 4

This solution uses the C++ standard library function reverse() to reverse a string.

• reverse() function is defined as a template in the header file <algorithm>.

• It reverses the order of elements in the range [first, last) of any container.

Complexity Analysis:

• $T=O(n)$$T = O(n)$

• $S=O(1)$$S = O(1)$

Solution:

xxxxxxxxxx
7
1
class Solution {
2
public:
3
    void reverseString(vector<char>& s) {
4
        // reverse the order of elements in the range [beg, end)
5
        reverse(s.begin(), s.end());    
6
    }
7
};