loading...

Reversing a string

danimal92 profile image Daniel Zaltsman ・2 min read

Here comes the next challenge: Reversing a string.

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.

Simple enough! Here was my first answer when I attempted it a few months ago.


return s.reverse()

Cheeky. But let's come up with our own solution.

So we cannot allocate memory to a new array, and we have to modify the array in-place. The first thing I do is look for a pattern. When reversing a string, the last letter is first, first is last, second to last is second, second is second to last, etc. This will be repeated until we hit the middle. It may be different odd/even length words, but we can account for that. Let's implement that solution!

var reverseString = function(s) {

for(let i = 0; i < s.length/2 ; i++){
        let prev = s[i]
        s[i] = s[s.length - 1 - i]
        s[s.length - 1 - i] = prev
    }
}

Let's break down this solution. On each character, we will save the current character, change the current character in the array to the character on the opposite side of the array, and then use the saved character to change the character on the further end.

In this solution, we only need one pointer, prev. The iterator variable i will increment until it hits the middle of the word. For odd numbered words the reversing will stop before it hits the one letter in the middle and for even numbered words it will continue until it reverses the last pair in the middle of the word.

Posted on by:

danimal92 profile

Daniel Zaltsman

@danimal92

Full stack developer with a passion for problem solving and creating products that are useful to the everyday consumer.

Discussion

markdown guide