Write a function that reverses a string. The input is given as an array of characters s
.
You must do this by modifying the input array in-place with O(1)
extra memory.
Constraints:
- $1 \leq s.length \leq 105$
s[i]
is a printable ascii character
Input: s = ["h","e","l","l","o"] Output: ["o","l","l","e","h"] Input: s = ["H","a","n","n","a","h"] Output: ["h","a","n","n","a","H"]
We can have two pointers left_idx = 0
and right_idx = len(s)
and swap s[left_idx]
and s[right_idx]
.
Then left_idx += 1
, right_idx -= 1
, until left_idx == right_idx
.
def reverseString(s):
"""
:type s: List[str]
:rtype: None Do not return anything, modify s in-place instead.
"""
left_idx = 0
right_idx = len(s) -1
while left_idx < right_idx:
s[left_idx], s[right_idx] = s[right_idx], s[left_idx]
left_idx += 1
right_idx -= 1
# tests
s = ["h","e","l","l","o"]
reverseString(s)
print(s == ["o","l","l","e","h"])
s = ["H","a","n","n","a","h"]
reverseString(s)
print(s == ["h","a","n","n","a","H"])
O(N)
O(1)
Recursion or two pointers.
<<imports for typing>>
See also: In-place algorithm.