1. Introduction
In this blog post, we tackle a fundamental problem in string manipulation with C++: reversing a string in place. This problem is essential for understanding array manipulation and pointers in C++, as well as the concept of in-place operations with minimal memory usage.
Problem
The challenge is to write a function that reverses a string. The input string is provided as an array of characters s. The reversal must be done in-place, meaning no additional arrays can be used, and the memory usage must be O(1).
2. Solution Steps
1. Use two pointers: one at the beginning of the string and the other at the end.
2. Swap the characters at these two pointers.
3. Move the pointers closer to each other: increment the start pointer and decrement the end pointer.
4. Continue this process until the two pointers meet or cross each other.
5. By doing this, we reverse the string in place without needing extra memory.
3. Code Program
#include <iostream>
#include <vector>
using namespace std;
// Function to reverse the string in place
void reverseString(vector<char>& s) {
int start = 0, end = s.size() - 1;
while (start < end) {
// Swap the characters
swap(s[start], s[end]);
start++; // Move the start pointer forward
end--; // Move the end pointer backward
}
}
int main() {
vector<char> s = {'h', 'e', 'l', 'l', 'o'};
reverseString(s);
cout << "Reversed string: ";
for (char c : s) {
cout << c;
}
cout << endl;
return 0;
}
Output:
Reversed string: olleh
Explanation:
1. The input array ['h', 'e', 'l', 'l', 'o'] is processed to reverse the string.
2. Two pointers, start and end, are used to traverse the string from both ends.
3. Characters at these pointers are swapped, and the pointers are moved towards each other.
4. The process continues until start and end meet, resulting in the string being reversed in place.
5. The final output "olleh" is the reversed form of the input string, achieved with O(1) extra memory.
Comments
Post a Comment