LeetCode 344. Reverse String

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)