Given a character array s, reverse the order of its elements in-place.
Table of Contents
Sample Input and Expected Output:
Input:
s = ['h', 'e', 'l', 'l', 'o']
Output:
Reversed string: ['o', 'l', 'l', 'e', 'h']
Input:
s = ['H', 'a', 'n', 'n', 'a', 'h']
Output:
Reversed string: ['h', 'a', 'n', 'n', 'a', 'H']
Reverse String Solution in C++:
The idea is to use a two-pointer approach. We use one pointer (left) starting from the beginning of the array and another pointer (right) starting from the end of the array. We swap the characters at these pointers and move left to the right and right to the left until they meet in the middle.
#include <iostream>
#include <vector>
void reverseString(std::vector<char>& s) {
int left = 0;
int right = s.size() - 1;
while (left < right) {
// Swap the characters at the left and right pointers.
std::swap(s[left], s[right]);
left++; // Move left pointer to the right.
right--; // Move right pointer to the left.
}
}
int main() {
std::vector<char> s1 = {'h', 'e', 'l', 'l', 'o'};
std::vector<char> s2 = {'H', 'a', 'n', 'n', 'a', 'h'};
reverseString(s1);
reverseString(s2);
std::cout << "Reversed string: [";
for (char ch : s1) {
std::cout << ch << " ";
}
std::cout << "]" << std::endl;
std::cout << "Reversed string: [";
for (char ch : s2) {
std::cout << ch << " ";
}
std::cout << "]" << std::endl;
return 0;
}
Time Complexity and Space Complexity:
The time complexity of the solution is O(n), where n is the size of the input vector s. This is because we use a two-pointer approach that traverses the array once.
The space complexity is O(1) as we are using a constant amount of additional space for variables in the solution, regardless of the size of the input array. The reversal is performed in-place, modifying the original array.