I need help with a reverse string

Question

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.

 

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"]

 

Constraints:

1. 1 <= s.length <= 105
2. s[i] is a printable ascii character.

Answer 1

The trick on this one is to use the extra memory word to hold a temporary value. Then you can swap the first and last values in the string, the second-to-first and second-to-last values, etc. One note of caution on this approach: if the string is very large, you may encounter paging problems which would affect efficiency.

There's also an elegant recursive algorithm for reversing a string, but it's not O(1). If you're interested, google "recursive string reverse".