Description

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.

Examples

Example 1:

Input: s = ["h","e","l","l","o"]
Output: ["o","l","l","e","h"]

Example 2:

Input: s = ["H","a","n","n","a","h"]
Output: ["h","a","n","n","a","H"]

Solution

class Solution {
public:
    void reverseString(vector<char>& s) {
        auto first = s.begin();
        auto last = prev(s.end());
        
        while (first < last) {
            char temp = *first;
            *first = *last;
            *last = temp;
            
            first++;
            last--;
        }
    }
};

Explanation

Pseudocode

procedure reverseString(S)
    B <- iterator to the beginning of S
    E <- iterator to the last elemenet of S
    
    while B < E do
        swap B with E
        
        B <- next(B)
        E <- prev(E)
    end while
end procedure

Improvement

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

When accessing an element in a vector, using integer indices can reduce runtime. Furthermore, c++ provides std::swap() function in algorithm standard library.