Repeat Code With LeetCode — Reverse Words In A String, Stack Solution
Last week’s problem was so fun that I decided to do it a second time…
If you look at the LeetCode solutions, you will find that the in-place solution is much more upvoted and popular than the stack solution. This still passes, though, and I honestly think that the ability to solve the problem with a stack (a fairly straightforward solution) says more about the candidate than the ability to come up with the in-place solution. I imagine in most real interviews, though, the stack solution would only be accepted as part one of the problem.
I did the in-place solution last week
I will do my best to make this blog post independent, but I recycled a LOT of code from last week.
The Problem
Reverse Words In A String
Difficulty: Medium
Skills Required: Stack (depending on implementation)
Description: Given an input string s, reverse the order of the words.
A word is defined as a sequence of non-space characters. The words in s will be separated by at least one space.
Return a string of the words in reverse order concatenated by a single space.
Note that s may contain leading or trailing spaces or multiple spaces between two words. The returned string should only have a single space separating the words. Do not include any extra spaces.
The Stack
Here’s what someone on StackOverflow has to say about the stack (overflow):
You’ve been to a cafeteria, right? and seen a stack of plates? When a clean plate is added to the stack, it is put on top. When a plate is removed, it is removed from the top. So it is called Last-In-First-Out (LIFO). A computer stack is like that, except it holds numbers, and you can make one out of an array or a list, if you like. (If the stack of plates has a spring underneath, they say you “push” one onto the top, and when you remove one you “pop” it off. That’s where those words come from.)
— Source
That’s the way I had it explained to me as well (a stack of plates), and I never thought it was the best analogy. You CAN take a plate other than the top plate out of a stack — you probably used to do this all the time when you grabbed enough plates to set up a table. It’s obviously easier to take the top plate than the bottom plate, but if you are a new student then the 30 seconds you took to understand the analogy was enough time for your competitor to buy Cracking The Coding Interview.
A way better analogy is a PEZ dispenser, but I’m not sure if everyone knows what that is
A stack is last-in first-out. You get things in reverse order. Another user on the same thread describes it like this:
Use a queue when you want to get things out in the order that you put them in.
Use a stack when you want to get things out in the reverse order than you put them in.
Use a list when you want to get anything out, regardless of when you put them in (and when you don’t want them to automatically be removed).
You can find operations defined in complexity on the big oh cheat sheet, but only this tells the whole story. Insertion and deletion are O(1), as is getting the top. But if you want some particular element in a stack, then you are probably more interested in an array.
Now if you examine the big oh cheat sheet a second time, you will notice that a stack shines in insertion/deletion compared to an array.
This problem is ideal because you retrieve items in reverse order.
The Solution
Like last week’s solution, this relies on the C++ pop_back function. You will insert every word in reverse order, but there will be an extra space at the end to get rid of.
Include a stack. If you want to roll out your own stack implementation then this is a much harder problem.
You can use a string stream to parse every individual word, put it into a stack, and then retrieve the words from the stack in reverse order.
Then return the string and you are done.
