344. Reverse String

• python3

📎 Probelm

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 <= s.length <= 105
• s[i] is a printable ascii character.

Pseudocode

1. Initialize two pointers:one at the beginning index and one at the end index.
2. Swap the elements at the poisition of the two pointers.
3. Increment the beginning pointer by one and decrement the end pointer by one.
4. Repeat these steps until the pointer meet or cross each other.

Code

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:
            s[i], s[j] = s[j], s[i]
            i+=1
            j-=1

Result

• Time Complexity: O(n) as we traverse the array only once.
• Space Complexity : O(1) as we don't use extra space.