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.
LeetCode Solutions1 <= s.length <= 105s[i] is a printable ascii character.The reverse method iterates through the array once to reverse it, resulting in a time complexity of , where n is the length of the array s.
Since the reverse method modifies the array in place, it does not require any additional space beyond a few temporary variables used internally by the method.
The built-in reverse() method reverses an array in place. It modifies the original array and returns a reference to the same array. In this case, we simply call s.reverse() to reverse the input array of characters.
Where n is the length of the array s. We need to iterate through half of the array to swap the characters.
Since we are modifying the array in place and only using a few temporary variables, the space complexity is .
In this approach, we use two pointers: one starting at the beginning of the array (left) and the other at the end of the array (right). We swap the characters at these two pointers using a temporary variable temp to hold one of the characters during the swap. After swapping, we move the left pointer one step to the right and the right pointer one step to the left. We continue this process until the left pointer is no longer less than the right pointer, which means we have reversed the entire array.
Where n is the length of the array s. We need to iterate through half of the array to swap the characters.
Since we are modifying the array in place and only using a few temporary variables, the space complexity is .
In this approach, we use two pointers: one starting at the beginning of the array (left) and the other at the end of the array (right). We swap the characters at these two pointers and then move the left pointer one step to the right and the right pointer one step to the left. We continue this process until the left pointer is no longer less than the right pointer, which means we have reversed the entire array.
Where n is the length of the array s. We need to iterate through half of the array to swap the characters.
Due to the recursive call stack. In the worst case, the depth of the recursion can be equal to the length of the array if the array is large.
In this approach, we define a helper function reverse that takes the array and two pointers (left and right). The function checks if the left pointer is greater than or equal to the right pointer, in which case it returns (base case). Otherwise, it swaps the characters at the left and right pointers and then recursively calls itself with the left pointer moved one step to the right and the right pointer moved one step to the left. This process continues until the base case is reached, effectively reversing the array.
Where n is the length of the array s. We need to iterate through the array twice: once to push characters onto the stack and once to pop characters from the stack and overwrite the original array.
Since we are using a stack to store all characters of the input array, the space complexity is , where n is the length of the array s.
In this approach, we use a stack data structure to reverse the string. We first push all characters of the input array s onto the stack. Then, we pop characters from the stack and overwrite the original array s with the popped characters. This effectively reverses the array since the last character pushed onto the stack will be the first one popped off.
| Approach | Rating | Time Complexity | Space Complexity | Advantages | Disadvantages |
|---|---|---|---|---|---|
| Using Built-in Reverse Method | Simplest and most concise — single line of code | Relies on language built-in, may not be accepted in interviews | |||
| Two Pointers with Temporary Variable | Classic interview approach, easy to understand, demonstrates core algorithm | Requires a temporary variable for swapping | |||
| Two Pointers with Array Destructuring | Eliminates temporary variable using destructuring syntax | May be less readable for beginners | |||
| Recursive Approach | Elegant recursive logic | Uses stack space, risk of stack overflow on large inputs | |||
| Using Stack | Demonstrates stack data structure usage | Requires extra space for the stack, two passes needed |
The optimal approach for this problem is Solution 2: Two Pointers with Temporary Variable, which achieves time complexity and space complexity. It is the classic two-pointer approach that clearly demonstrates the core algorithm, making it ideal for interviews and easy to understand.
class Solution: def reverseString(self, s: List[str]) -> None: """ Do not return anything, modify s in-place instead. """ s.reverse()class Solution: def reverseString(self, s: List[str]) -> None: """ Do not return anything, modify s in-place instead. """ left = 0 right = len(s) - 1
while left < right: temp = s[left] s[left] = s[right] s[right] = temp
left += 1 right -= 1class Solution: def reverseString(self, s: List[str]) -> None: """ Do not return anything, modify s in-place instead. """ left = 0 right = len(s) - 1
while left < right: # Swap characters at left and right pointers using Tuple unpacking s[left], s[right] = s[right], s[left]
left += 1 right -= 1class Solution: def reverseString(self, s: List[str]) -> None: """ Do not return anything, modify s in-place instead. """ self.reverse(s, 0, len(s) - 1)
def reverse(self, stringArray: List[str], left: int, right: int) -> None: if left >= right: return
temp = stringArray[left] stringArray[left] = stringArray[right] stringArray[right] = temp
self.reverse(stringArray, left + 1, right - 1)class Solution: def reverseString(self, s: List[str]) -> None: """ Do not return anything, modify s in-place instead. """ stack = []
# Push all characters onto the stack for char in s: stack.append(char)
# Pop characters from the stack and overwrite the original array for i in range(len(s)): s[i] = stack.pop()