In-Place String Reversals

avatar
Marshal Murphy
June 05, 2020 - 2 MIN READ

The Problem: Given a string, write a function to return the string reversed.

In-Place String Reversals

In-place algorithms, sometimes called destructive algorithms, work by modifying the input data structures themselves.

Said another way, when given a string, and in-place algorithm will permanently change that string.


In-Place Algorithms

We can draw an example of in-place behaviour by comparing the internal JavaScript functions slice() and splice().

On one hand, slice creates a shallow copy of a portion of an array without changing the original array.

Conversely, splice permanently changes the original array by removing and/or adding values to it, and therefore operates in-place.


Approach

Given a string, how would we approach creating a function that will reverse the string in-place?

Typically, in-place algorithms will require swapping elements.

We can work through the string letter by letter by splitting it into an array, swapping the first letter with the last letter, the second with the second last, and so one.

To do this we will use indices to track our progress until they meet in the centre.

Computationally this will only be on the order of O(n) time.


JavaScript

With node installed on your machine, open the command line and launch the node CLI to test this JavaScript:

> node

Paste in our function above and test it by passing various strings to see the output.

javascript test


Ruby

We can run interactive ruby from the command line by entering irb, just like how we did with node.

> irb

Paste in the above function and test by passing in various strings to see the input reversed.

ruby test


Learnings

Modifying data in-place is useful.

Just keep in mind that you are permanently altering the data received by the function. 😉

Marshal Murphy 2020