Abstract / Summary

Given a sentence, reverse the order of the words and return the new sentence with words separated by a single space.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 57% (5+ million submissions).

Typical patterns to solve this problem:

• String
• Two Pointers

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation defines a Solution class with a single public method reverseWords. The method receives a standard C++ string containing a sequence of words separated by whitespace. Its purpose is to produce a new string where the order of the words is reversed while preserving a single space between each word. The algorithm leverages the C++ standard library’s stringstream to tokenize the input and builds the result by prepending each extracted word.

Key Steps

The core logic can be broken down into three distinct operations, each illustrated with the corresponding code fragment.

Tokenization with stringstream

stringstream text;
text.str(s);

A stringstream object named text is created and initialized with the input string s. By feeding the entire input into the stream, the subsequent extraction operator (>>) will automatically split the string on any whitespace characters, handling spaces, tabs, and newlines uniformly.

Iterative Extraction and Prepending

string result, word;
while (text >> word)
{
    if (!result.empty())
        result = word + ' ' + result;
    else
        result = word;
}

Inside a while loop, each word is read from the stream into the variable word. The loop continues until no more tokens are available. For each iteration, the algorithm checks whether result already contains content. If it does, the new word is placed before the existing content, separated by a single space. If result is still empty (i.e., processing the first word), the word is assigned directly without a leading space. This approach constructs the reversed sequence incrementally without requiring an auxiliary container to hold all words.

Returning the Final String

return result;

After all tokens have been processed, the method returns the assembled result string, which now holds the words in reverse order.

Edge Cases Handled

The implementation naturally accommodates several edge conditions due to the behavior of stringstream and the conditional logic used when building result.

When the input string is empty, the stream yields no tokens, the loop body never executes, and result remains an empty string, which is returned directly. This matches the expectation that reversing an empty sequence yields an empty result.

If the input consists solely of whitespace characters, the extraction operator skips over all whitespace and produces no tokens. Consequently, the method again returns an empty string, effectively trimming leading, trailing, and intermediate whitespace.

Multiple consecutive whitespace characters between words are collapsed by the extraction operator, which treats any run of whitespace as a single delimiter. The resulting output contains exactly one space between each reversed word, regardless of the original spacing.

A single-word input bypasses the prepend logic because result is empty on the first iteration. The word is assigned directly, and the loop ends, returning the original word unchanged, which is the correct reversed order for a solitary element.

Performance Optimizations Observed

The algorithm avoids allocating additional containers such as vectors or lists to store intermediate words. By directly prepending each word onto the result string, it eliminates the need for a separate reversal pass. This in-place construction reduces memory overhead and keeps the number of allocations low, especially when the number of words is modest.

The use of stringstream for tokenization provides a concise and efficient means of parsing whitespace-separated tokens without manual character scanning. The extraction operator internally employs optimized parsing routines, which can be faster than a custom loop that examines each character.

Conditional concatenation (if (!result.empty())) ensures that a space character is added only when necessary, preventing the creation of an extra leading space. This small check eliminates the need for post-processing to trim unwanted whitespace, thereby saving an additional pass over the string.

Overall, the method achieves the reversal with a single pass over the input stream and incremental string building, resulting in a streamlined execution path that leverages standard library efficiencies.

Imagine you have a row of colorful building blocks, and each block has a different word written on it. This code is like a magical robot that picks up those blocks one by one from the very beginning of the row. Every time the robot picks up a new word, it places it down in front of the words it already gathered. If the robot already has a little train of words, it puts a tiny space between the new word and the rest of the group. By the time the robot reaches the end of the line, all the words are sitting in the opposite order from how they started. The first word is now at the very back, and the last word is at the very front.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

not analyzed yet

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++	Python	Java				TS
	WalkCCC	C++	Python	Java
	leetcode.ca	C++	Python	Java	C#			TS		Rust		Go
	LeetcodeHelp	C++	Python	Java
	MemoryLimitExceeded	C++	Python
	Progiez	C++	Python	Java
github	aylei									Rust
	begeekmyfriend					C
	BigEggStudy				C#
	black-shadows	C++
	chandansgowda		Python
	charles-wangkai			Java
	chenyanzhe	C++
	Dijkstra-Edu			Java
	everthis						JS
	fartem										Ruby
	fengvyi	C++
	gaosq0604		Python
	gouthampradhan			Java
	halfrost											Go
	haoel	C++
	JoshCrozier						JS
	keineahnung2345	C++
	lennylxx					C
	linouk23	C++
	lkwq007		Python
	luangong	C++						TS
	MacJim	C++
	martianoff								Scala
	pruthvikp		Python
	qiyuangong		Python
	shreymehul				C#
	sonugiri1043	C++
	suxrobGM				C#
	trung-hn		Python
	varunu28			Java
	vli02					C
	vthwang			Java
	XiaotaoGuo	C++
	zfang399	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, C#, Go, Java, Python, Rust, TypeScript
LeetcodeHelp	C++, Java, Python
MemoryLimitExceeded	Python, C++
Progiez	C++, Java, Python
aylei	Rust
begeekmyfriend	C
BigEggStudy	C#
black-shadows	C++, C++
chandansgowda	Python
charles-wangkai	Java
chenyanzhe	C++
Dijkstra-Edu	Java
everthis	JavaScript
fartem	Ruby
fengvyi	C++
gaosq0604	Python
gouthampradhan	Java
halfrost	Go
haoel	C++
JoshCrozier	JavaScript
keineahnung2345	C++
lennylxx	C
linouk23	C++
lkwq007	Python
luangong	C++, TypeScript
MacJim	C++
martianoff	Scala
pruthvikp	Python
qiyuangong	Python
shreymehul	C#
sonugiri1043	C++
suxrobGM	C#
trung-hn	Python
varunu28	Java
vli02	C
vthwang	Java
XiaotaoGuo	C++
zfang399	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality