Dare2Solve
The problem requires reversing a string, represented as an array of characters, in-place. We need to swap the characters without using additional memory for another array. The goal is to reverse the input array with minimal space complexity.
Reversing a string can be visualized as swapping the first character with the last, the second character with the second-to-last, and so on, until the entire array is reversed. By using two pointers, one starting from the beginning and the other from the end, we can efficiently swap elements and reduce the number of operations.
i
at the beginning of the array and j
at the end.i
and j
.i
and decrement j
to move towards the center of the array.O(n), where n
is the length of the array. Each character is swapped once, and we traverse half the array due to the two-pointer approach.
O(1), since we only use a constant amount of extra space for the two pointers and the temporary variable during swapping.
class Solution {
public:
void reverseString(vector<char>& s) {
int i = 0, j = s.size() - 1;
while (i < j) {
char temp = s[i];
s[i] = s[j];
s[j] = temp;
i++;
j--;
}
}
};
class Solution:
def reverseString(self, s: list[str]) -> None:
i, j = 0, len(s) - 1
while i < j:
s[i], s[j] = s[j], s[i]
i += 1
j -= 1
class Solution {
public void reverseString(char[] s) {
int i = 0, j = s.length - 1;
while (i < j) {
char temp = s[i];
s[i] = s[j];
s[j] = temp;
i++;
j--;
}
}
}
/**
* @param {character[]} s
* @return {void} Do not return anything, modify d in-place instead.
*/
var reverseString = function(d) {
let j = d.length - 1 , i = 0;
while(i < j){
const Lle = d[i];
d[i] = d[j]
d[j] = Lle;
j--;
i++;
}
};