Today’s practice algorithm question is to reverse string in-place. Another good practice for your problem-solving mindset.
Article Contents
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 ~
