Reverse String In-Place

0
69
Reverse String In-Place
Reverse String In-Place

Today’s practice algorithm question is to reverse string in-place. Another good practice for your problem-solving mindset.

Problem

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:

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

Analysis

Without considering the in-place constraint, we can do by creating a new array with equal size of given input, then continuously add characters from last position to first position into result array.

With in-place, we can think of swapping position of last and first position, n - 2 with 2 position … and we stop when it reaches the middle point of array.

Solution

Here the solution in Java.

public void reverseString(char[] s) {
    char t = 0; // temp variable to hold for swapping
    for (int i = 0; i < s.length/2; i++) {
        t = s[i];
        s[i] = s[s.length - 1 - i];
        s[s.length-1-i] = t;
    }
}

We use only two extra variables char t and int i, so the space is a constant, which satisfies the condition O(1) space.

Apparently, we can use two pointers to run on both sides of array towards the mid-point.

References

Have fun ~