Welcome back!
I am starting to work my way through this repository of algorithm problems from Learn-Co. It starts off easy, which is great for people who may be new to algorithms.
So, I thought I could, ahem, re-start at the beginning, too. I know I have previously presented some more challenging problems, but I'm headed back to basics for a bit.
If you'd like to try the problem yourself first, you can find it in the above linked repository or here:
* This version is slightly different in expectation. More on this later.
The Problem
The Reverse String algorithm problem is as follows:
Given a string
s
, returns
in reverse. Do not use any built-in reverse method.
Example
s
=hello world
output =dlrow olleh
The Approach
Before I get into my approach, I need to address the LeetCode version of this problem, which asks for you to solve the problem "in-place", meaning "mutate the original string."
I am solving these problems in JavaScript, and in JavaScript, strings are immutable. This means it is not possible to reverse a string in-place. There's a reason the LeetCode version of this problem has to use an array of characters instead of a string. Since an array of strings is not itself a string, and our our problem is how to reverse a string, not an array, that is the problem we will solve. 😤
That being said, if the problem you are given is to reverse an array in-place, (which is what the LeetCode version of this problem is,) the solution I am going over here is not the most optimized version. Check out the two-pointer technique, instead.
Okay, back to the program.
In this approach, we will initialize a new variable, reversed
, as an empty string. We will then loop over s
backwards, adding each character to reversed
inside of the loop.
Time Complexity: O(n)
Why?
There is a single for
loop. The time it takes to compute the solution will grow directly with the length of our input string, s
. Thus, n
represents the length of s
.
Space Complexity: O(n)
Why?
We are creating a variable, reversed
, that will be the length of s
. This means the memory consumed to solve the algorithm is directly related to the length of s
. Thus, n
represents the length of s
.
Variables Used:
-
reversed
- An empty string to which we will add characters froms
. -
i
- Ourfor
loop counter. It will initially point to the last index ofs
so we can loop backwards.
Line-by-Line Walkthrough:
function reverseString {...}
-
Initialize variable
reversed
as an empty stringshow
let reversed = "";
-
Create a
for
loop which will iterate through the length ofs
backwards. Initialize variablei
with value ofs.length-1
, set the loop exit condition to be wheni
is equal to0
, and decrementi
each iteration. Backwards looping!show
for (let i = s.length-1; i >=0; i--) {...
-
Inside of the loop, redefine
reversed
to bereversed
+ the current character we are at ins
.show
reversed += s[i]
-
Once the loop has finished, return
reversed
.show
return reversed
Show Me The Logs
Here are my console.logs for this problem.
For the best experience, view them on replit, where you can fork it and feed your own inputs into the function!
🚀 🚀 🚀 REVERSE A STRING STARTING NOW 🚀 🚀 🚀
__________________________________________________
📥 s = "hello world"
============ LOOP 1 OF 11 ============
s = "hello world"
reversed = ""
i = 10
s[i] = "d"
============ LOOP 2 OF 11 ============
s = "hello world"
reversed = "d"
i = 9
s[i] = "l"
============ LOOP 3 OF 11 ============
s = "hello world"
reversed = "dl"
i = 8
s[i] = "r"
============ LOOP 4 OF 11 ============
s = "hello world"
reversed = "dlr"
i = 7
s[i] = "o"
============ LOOP 5 OF 11 ============
s = "hello world"
reversed = "dlro"
i = 6
s[i] = "w"
============ LOOP 6 OF 11 ============
s = "hello world"
reversed = "dlrow"
i = 5
s[i] = " "
============ LOOP 7 OF 11 ============
s = "hello world"
reversed = "dlrow "
i = 4
s[i] = "o"
============ LOOP 8 OF 11 ============
s = "hello world"
reversed = "dlrow o"
i = 3
s[i] = "l"
============ LOOP 9 OF 11 ============
s = "hello world"
reversed = "dlrow ol"
i = 2
s[i] = "l"
============ LOOP 10 OF 11 ============
s = "hello world"
reversed = "dlrow oll"
i = 1
s[i] = "e"
============ LOOP 11 OF 11 ============
s = "hello world"
reversed = "dlrow olle"
i = 0
s[i] = "h"
======== 🏁 Finished Looping 🏁 ========
🌟 🌟 🌟 Final Solution 🌟 🌟 🌟
The reversed version of "hello world" is "dlrow olleh"!
Solution
Finally, if you'd like to see a clean, log-free version of the solution, here it is:
View Solution
function reverseString(s) {
let reversed = "";
for (let i = s.length - 1; i >= 0; i--) {
reversed += s[i]
}
return reversed;
}
Thanks for reading and I wish you luck on whatever algorithmic endeavor brought you to this post. ♥
Top comments (0)