Repeat Code With LeetCode — Reverse Words In A String
Flashback to a problem set from my first quarter of my first year of college
There are a couple of reasons this was a relevant problem. First, “Reverse words in a string” builds perfectly from last week’s easy LeetCode question, “reverse string.”
Both involve the Two Pointer Technique, one can be used as a verbatim helper function for the other, and…wow! Talk about a blast from the past!
I notice my ECS30 problem set is still up. If anyone ever takes it down for any reason, it reads:
“Write a program that takes a data line at a time and reverses the words of the line. For examples,
Input: birds and bees
Reversed: bees and birds
The data should have one blank between each pair of words.”Additional Specifications:
Since gets() is unsafe, and causes a warning, you should use fgets with stdin as the FILE* to read the entire line
I wish I could write that I remember this period of my life fondly and laugh now at how easy the problem is in hindsight…but I can’t, this problem set required students to use C. I dug through some old Piazza questions, and I am now convinced that the only way I can exorcise this demon from my past is by solving it again in C.
At…some point. Not today.
The Problem
Difficulty: Medium
Skills Required: Two Pointer Technique (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.
Initial Thoughts
I imagine if past Evan asked present Evan for help with this problem, our conversation would go a little bit like this:
Past Evan: I am so lost and frustrated. What do I do?
Present Evan: I guess you could use a stack
Past Evan: What’s a stack? This is the first programming class. We don’t know data structures and are probably not allowed to use them
Present Evan: Use the Two Pointer Technique, which they explain on LeetCode
Past Evan: What’s LeetCode? Also, I need to solve this in C
Present Evan: Oh, I don’t know…ask ChatGPT
Past Evan: What?
Present Evan: What?
A stack works, and it’s probably the most intuitive solution.
The other idea is a lot more clever…it was taken from him, who in turn referenced this blog post. Arden writes:
Reverse all the characters in the string, then reverse the letters of each individual word. This can be done in-place using C or C++.
How do you go from
birds and bees
to
bees and birds
?
I can see why past Evan was confused and didn’t even know where to start, but you can reverse each word one-by-one.
sdrib dna seeb
Now reverse the whole thing.
bees and birds
That’s it. It’s clever, it’s clean, and it’s an in-place solution that utilizes the Two Pointer Technique.
The Solution
Lines 3–16 are a direct copy pasta from my reverse string solution. The idea is that you can reverse a string in-place by swapping the first character with the last character. It may have worked to do the much more intuitive thing and build a new string backwards, but technically that would be violating a constraint of this solution.
I don’t know if it was necessary to cite while(iss >> s), but I didn’t remember how to do that off the top of my head. The start of reverseWords() utilizes a StringStream to extract one word at a time.
Then I used pop_back, which was a bit messy…just to get rid of the last character.
Once I had the entire reversed string, I plugged the entire thing back into my reverse function.
