344. Reverse String.md

344. Reverse String

1. Description

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

2. Solutions

Solution 1: Language: C Two Pointers

One pointer is from the start of the array, and another one is from the end. Swap values and move these pointers to the next one.

• Sunday, 23 August, 2020
• Time Complexity: $O(n)$
• Space Complexity: $O(1)$
• Runtime: 52 ms, faster than 48.10% of C online submissions for Reverse String.
• Memory Usage: 12.4 MB, less than 15.11% of C online submissions for Reverse String.

void reverseString(char* s, int sSize) {
    int head = 0;
    // The last element of string is '\0'.
    int tail = sSize - 1;
    while (head < tail) {
        // Swapping two characters.
        int temp = s[head];
        s[head] = s[tail];
        s[tail] = temp;
        head++;
        tail--;
    }
}

Solution 2: Language: Python One Line with an Inbuilt Method

It is the best method when working, but the worst crap for learning.

• Sunday, 11 October, 2020
• Time Complexity: $O(n)$
• Space Complexity: $O(1)$
• Runtime: 156 ms, faster than 98.03% of Python online submissions for Reverse String.
• Memory Usage: 21.2 MB, less than 5.72% of Python online submissions for Reverse String.

class Solution(object):
    def reverseString(self, s):
        """
        :type s: List[str]
        :rtype: None Do not return anything, modify s in-place instead.
        """
        s.reverse()