String reversal is a common algorithm challenge and seemingly pretty straightforward. Given a string, you’re asked to find a solution that will return a new string with all characters in reverse order. For example, the string “abc” will return as the reversed string “cba”. This post will go over a few different methods in JavaScript to solve this algorithm, and briefly go over time complexity for each solution.
Example 1: split, reverse, join
The first solution is to use JavaScript’s built-in methods: split, reverse, and join. To clarify, these methods do the following:
- Split() separates a string into individual substrings. In the parenthesis, you can specify how you want these substrings separated. For this example, we’ll pass in quotation marks; either “” or ‘’ is accepted.
- Reverse() will “reverse an array in place”. For this example, we won’t pass in any argument in the parenthesis.
- Join() is another native method in JavaScript that “creates and returns a new string by concatenating all of the elements in an array”.
Simply put, the .split(“”).reverse().join(“”) method will do the following: the string “abc” will become [“a”, “b”, “c”], then [“c”, “b”, “a”], then “cba”.
Running this approach 3 times gave me three different runtimes. I took the average of the three, so the runtime (for this post) is 0.118ms.
Note: while this is a perfectly fine solution, I’d advise you ask the interviewer whether or not you’re allowed to use built in methods before beginning, as each interview is different.
Example 2: For loop
We can use a for loop and iterate a string starting from the last character. You’ll initiate a counter variable (I used i in this case), assign it the value of the last character in the string, and it will continue decrementing each iteration until it is greater than or equal to the string at the zeroth index.
A for loop typically has a time complexity of O(N); as input increases, so does runtime. In our current case, as the string gets lengthier, it will take longer for our local machines to run through the string and concatenate to the new string.
Again, using console.time to test this approach, my average runtime was 0.179ms. Once I scale up, a for loop may not be ideal. For this example, though, a for loop works fine.
Example 3: Recursion
We can use recursion to solve this algorithm. In recursion, we need a base case so our function knows when to end, and to invoke our function once again, with some change to our initial arguments — for the most part.
Using recursion, we will set our base case to an empty string. We will return the function where we create a substring from the string argument starting at the first index which concatenates with the string’s zeroth index character. So, in the example of “abc”, our first iteration will be “b” + “a”, which returns “ba”. In our final iteration, we have the sole character, “c”, which then concatenates with the previous string, “ba”. Now, the string is empty, so we simply return “”.
Recursion almost always has the worst time complexity. We’re essentially having a function invoke itself repeatedly until the base case is met (and if not careful, we’ll exceed the maximum call stack). There are a number of instances, however, where solving a challenge recursively is optimal compared to solving it iteratively, although we won’t dive into that in this post.
In this case, the average runtime was 0.115 ms.
Example 4: Using reduce
Reduce is, in my opinion, a really efficient way of concatenating, and not a method I thought about using prior to this blog. Using reduce, we iterate through the string, first by splitting each character into subarrays. Then, we specify that the individual subarrays are concatenated starting at the last.
Built-in methods such as map(), filter(), reduce() “were introduced in ES5”, and are considered to be more time efficient than for loops. Yotam Kadishay makes a point, though, that reduce is still “a callback function”, which can contribute to a slightly longer run time. For this example, the average runtime using reduce was 0.112ms.
As you can see, there are many ways of reversing a string. Likewise, there are many ways of approaching an algorithm. While this blog doesn’t incorporate all solutions, I hope it shed light on creative ways to reverse a string, keeping in mind the time complexity of each approach.
