Description
https://leetcode.com/problems/reverse-string/
Write a function that reverses a string. The input string is given as an array of characters char[].
Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.
You may assume all the characters consist of printable ascii characters.
Example 1:
Input: ["h","e","l","l","o"] Output: ["o","l","l","e","h"]
Example 2:
Input: ["H","a","n","n","a","h"] Output: ["h","a","n","n","a","H"]
Explanation
Keep swapping one character from the beginning and one character from the end.
Python Solution I
class Solution:
def reverseString(self, s: List[str]) -> None:
"""
Do not return anything, modify s in-place instead.
"""
i = 0
j = len(s) - 1
while (i < j):
temp = s[i]
s[i] = s[j]
s[j] = temp
i = i + 1
j = j - 1- Time complexity: O(N)
- Space complexity: O(1)
Python Solution II
class Solution:
def reverseString(self, s: List[str]) -> None:
"""
Do not return anything, modify s in-place instead.
"""
self.helper(s, 0, len(s) - 1)
def helper(self, s, i, j):
if i >= j:
return
char = s[i]
s[i] = s[j]
s[j] = char
self.helper(s, i + 1, j - 1)- Time Complexity: O(N)
- Space Complexity: O(N)