LeetCode 151 - Reverse Words in a String
The problem asks us to take a string s containing words separated by spaces and return a new string where the words appear in reverse order. A word is defined as any sequence of non-space characters, and words can be separated by multiple spaces.
Difficulty: 🟡 Medium
Topics: Two Pointers, String
Solution
Problem Understanding
The problem asks us to take a string s containing words separated by spaces and return a new string where the words appear in reverse order. A word is defined as any sequence of non-space characters, and words can be separated by multiple spaces. The output must normalize spaces so that only a single space exists between words, and no leading or trailing spaces remain.
The input string can contain uppercase and lowercase English letters, digits, and spaces, and its length can be up to 10,000 characters. The problem guarantees that there is at least one word, so an empty input string does not need handling. Important edge cases include multiple consecutive spaces, leading or trailing spaces, and a single word string.
A naive solution might ignore extra spaces or fail to properly reverse the words. The follow-up challenge asks for an in-place solution if the string is mutable, with O(1) extra space.
Approaches
Brute Force
A straightforward brute-force approach is to split the string into words using a built-in method (e.g., split() in Python or strings.Fields in Go), which automatically removes extra spaces. Then, reverse the list of words and join them with a single space. This approach is simple and correct but uses additional memory proportional to the number of words because a new list or slice is created. For very long strings, this extra space could be significant.
Optimal Approach
The optimal approach uses the two-pointers technique to reverse words in-place if the string is mutable, or at least with minimal extra space. The key insight is that reversing the entire string and then reversing each word individually achieves the desired order. This works because reversing all characters moves words into reverse positions, and reversing characters within each word restores the correct word spelling. Additional steps are required to remove extra spaces efficiently.
| Approach | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Brute Force | O(n) | O(n) | Split into words, reverse list, join |
| Optimal | O(n) | O(1) extra (if mutable) | Reverse whole string, then reverse each word, trim spaces |
Algorithm Walkthrough
- Trim and normalize spaces: Remove leading and trailing spaces and reduce multiple spaces between words to a single space. This ensures consistent processing.
- Reverse the entire string: Treat the string as an array of characters and reverse all characters. This moves words into reversed positions.
- Reverse each word individually: Iterate through the reversed string, identify each word by scanning for spaces, and reverse characters of each word. This restores the correct spelling of each word.
- Join words with a single space: After all words are reversed, the final string will have words in the correct reverse order with single spaces separating them.
Why it works: Reversing the entire string moves words to the opposite end while reversing each word individually restores each word to its correct order. Combined, these two operations reverse the order of words while keeping their internal characters intact.
Python Solution
class Solution:
def reverseWords(self, s: str) -> str:
# Step 1: Trim and normalize spaces
words = s.strip().split()
# Step 2: Reverse the list of words
reversed_words = words[::-1]
# Step 3: Join with single space
return ' '.join(reversed_words)
Explanation:
First, strip() removes leading and trailing spaces. split() automatically splits on whitespace and collapses multiple spaces between words. Reversing the list with slicing [::-1] changes the order of the words. Finally, ' '.join() constructs the result string with single spaces between words.
Go Solution
import "strings"
func reverseWords(s string) string {
// Step 1: Trim spaces and split by whitespace
fields := strings.Fields(s)
// Step 2: Reverse the slice of words
for i, j := 0, len(fields)-1; i < j; i, j = i+1, j-1 {
fields[i], fields[j] = fields[j], fields[i]
}
// Step 3: Join words with single space
return strings.Join(fields, " ")
}
Explanation:
Go does not have a built-in string reverse, so we reverse the slice of words manually with a two-pointer swap. strings.Fields automatically handles trimming and collapsing multiple spaces. strings.Join joins the words with a single space. The logic mirrors the Python solution closely.
Worked Examples
Example: s = " hello world "
- Trim and normalize spaces →
["hello", "world"] - Reverse words →
["world", "hello"] - Join →
"world hello"
Example: s = "a good example"
- Trim and normalize →
["a", "good", "example"] - Reverse words →
["example", "good", "a"] - Join →
"example good a"
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | O(n) | Each character is processed at most twice: once during split/scan and once during join/reverse. |
| Space | O(n) | Brute force uses a list or slice of words; optimal in-place approach reduces extra space if mutable. |
The dominant factor is string length n, which can be up to 10,000. Splitting and joining operations require linear time and space in the number of characters.
Test Cases
# Provided examples
assert Solution().reverseWords("the sky is blue") == "blue is sky the"
assert Solution().reverseWords(" hello world ") == "world hello"
assert Solution().reverseWords("a good example") == "example good a"
# Boundary tests
assert Solution().reverseWords("single") == "single" # single word, no spaces
assert Solution().reverseWords(" leading") == "leading" # leading spaces
assert Solution().reverseWords("trailing ") == "trailing" # trailing spaces
assert Solution().reverseWords(" multiple spaces here ") == "here spaces multiple"
assert Solution().reverseWords(" ") == "" # only spaces, but problem guarantees at least one word
| Test | Why |
|---|---|
| "the sky is blue" | Normal input with multiple words |
| " hello world " | Leading and trailing spaces |
| "a good example" | Multiple spaces between words |
| "single" | Single word, edge case |
| " leading" | Leading spaces only |
| "trailing " | Trailing spaces only |
| " multiple spaces here " | Complex spacing scenario |
Edge Cases
Single word: Input like "single" should return "single". No spaces exist to remove or reverse.
Multiple spaces between words: Input like "a b" must be normalized to "b a". Splitting on whitespace handles this automatically.
Leading and trailing spaces: Input like " hello" or "world " must be trimmed to remove extra spaces. The solution uses strip() in Python and strings.Fields in Go, ensuring no leading or trailing spaces appear in the output.
Empty or all-space string: Even though the problem guarantees at least one word, a defensive implementation ensures it does not fail on " " or empty string inputs. The split operation safely returns an empty list, and join returns an empty string, which would be consistent with normalized output.