The Leetcode July Challenge we’re looking at today is a string manipulation problem, Reverse Words in a String. For this problem we’re asked to create an algorithm that takes an input string and returns a string with the words from the input string in reverse order, each separated by a single space, with no leading or trailing whitespace on the string. Let’s see what that means with some examples.

The basic case: “reverse words in a string”

The leading/trailing whitespace case: “    reverse words in a string    ”

The extra internal whitespace case: “reverse     words in     a string”

Should all output: “string a in words reverse”

My first instinct when working on a problem that requires trimming whitespace and/or tokenizing a string with C++ is to use a stringstream object, so that’s what I’ll use for this problem. There’s a perfectly good way to handle this problem just using index pointers, but I guess this problem hit my lazy bone. The stringstream makes both of the input tasks easy, so then we just have to decide how to handle rearranging the words in reverse order. I tried a few different approaches:

For my first approach, I just tried to build the output string directly with sparse code, but you’ll catch the downside:

string reverseWords(string s) {
   string temp;
   istringstream iss(s);
   s.clear();
   while(iss >> temp) {
	  s = temp + " " + s;
   }
   // pop the extra whitespace from the back.
   if(s.length()) s.pop_back();
   return s;
}

The frequent memory allocations to the front of the string aren’t great though. So, we can try bulding the string front to back, only appending to the back, by reverse each word then reversing the string.

string reverseWords(string s) {
   string reversed;
   istringstream iss(s);
   while(iss >> s) {
	  reverse(s.begin(),s.end());
	  reversed += s + " ";
   }
   // pop the extra whitespace from the back.
   if(reversed.length()) reversed.pop_back();
   reverse(reversed.begin(), reversed.end());
   return reversed;
}

Those repeated reverse calls aren’t great either though. I finally settled on a stack based solution where we just push each word onto the stack and them pop them off in reverse order. I’m not in love with this algorithm and its additional memory use, but I think it’s the preferable of the three I tried.

string reverseWords(string s) {
   istringstream iss(s);
   stack<string> stringStack;
   while(iss >> s) {
	  stringStack.push(s);
   }
   string reversed;
   while(!stringStack.empty()) {
	  reversed += " " + stringStack.top();
	  stringStack.pop();
   }
   // if string is non-empty, there will be an extra whitespace at index 0.
   return reversed.length() ? reversed.substr(1) : reversed;
}

Well, this was probably the problem I’ve been most dissatisfied with myself on this month, but those are going to happen occasionally, and I’ll probably revisit it after I’ve let it simmer a while. A fun sidenote is that while I prefer not to use Python for algorithms–because it abstracts away a lot of what I’m trying to understand–my first thought on seeing this problem is a super convenient Python one-liner worth knowing.

def reverseWords(self, s: str) -> str:
	return " ".join(reversed(s.split()));

Split the string into a list of words. Reverse the list. Join list items separated by a single space. Beautiful!