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 in Python
Approach:
- Two-Pointer Technique:
- We use two pointers: one starting at the beginning of the list and the other at the end.
- We swap the characters at these two positions and then move the pointers towards each other: the left pointer moves right, and the right pointer moves left.
- This continues until the two pointers meet or cross each other, at which point the entire string has been reversed.
- In-Place Operation:
- We modify the input list directly, so no additional space is needed beyond the two pointers (which is O(1) extra memory).
Python
class Solution:
def reverseString(self, s: List[str]) -> None:
"""
Do not return anything, modify s in-place instead.
"""
# Initialize two pointers
left, right = 0, len(s) - 1
# Continue until the left pointer meets the right pointer
while left < right:
# Swap the characters at the left and right pointers
s[left], s[right] = s[right], s[left]
# Move the pointers towards the center
left += 1
right -= 1Explanation:
- Initialization:
- The
leftpointer is initialized to 0 (the start of the list), and therightpointer is initialized tolen(s) - 1(the end of the list).
- The
- Swapping:
- In the
whileloop, we swap the characters at theleftandrightindices using the Python multiple assignments[left], s[right] = s[right], s[left].
- In the
- Moving Pointers:
- After swapping, we increment the
leftpointer and decrement therightpointer, gradually moving towards the center of the list.
- After swapping, we increment the
- Termination:
- The loop terminates when
leftis no longer less thanright, meaning all characters have been swapped.
- The loop terminates when
Solution in C++
C++
class Solution {
public:
// Function to reverse the input vector of characters
void reverseString(vector<char>& s) {
// Initialize two pointers: one at the start and one at the end of the array
int left = 0;
int right = s.size() - 1;
// Swap the characters while the two pointers haven't crossed each other
while (left < right) {
// Swap the characters at the left and right positions
swap(s[left], s[right]);
// Move the left pointer to the right
left++;
// Move the right pointer to the left
right--;
}
}
};Solution in Javascript
JavaScript
var reverseString = function(s) {
// Initialize two pointers, one at the start and one at the end of the array
let left = 0; // points to the first character
let right = s.length - 1; // points to the last character
// Continue swapping while the left pointer is less than the right pointer
while (left < right) {
// Swap the characters at the left and right pointers
let temp = s[left];
s[left] = s[right];
s[right] = temp;
// Move the left pointer to the right
left++;
// Move the right pointer to the left
right--;
}
};Solution in Java
Java
class Solution {
public void reverseString(char[] s) {
// Initialize two pointers: one at the start and one at the end of the array
int left = 0;
int right = s.length - 1;
// Continue swapping until the pointers meet in the middle
while (left < right) {
// Swap characters at left and right indices
char temp = s[left];
s[left] = s[right];
s[right] = temp;
// Move the left pointer towards the center
left++;
// Move the right pointer towards the center
right--;
}
}
}