Reverse Words in a String III
Problem
Given a string s, reverse the order of characters in each word within a sentence while preserving whitespace and initial word order.
- 1 ≤ s.length ≤ 5 * 10⁴
- s contains printable ASCII characters.
- s does not contain leading or trailing spaces.
- All words are separated by a single space.
Example
s = "Let's take LeetCode contest""s'teL ekat edoCteeL tsetnoc"The algorithm splits the input string into words: ["Let's", "take", "LeetCode", "contest"]. It reverses each word individually: "Let's" → "s'teL", "take" → "ekat", "LeetCode" → "edoCteeL", "contest" → "tsetnoc". Finally, it joins the reversed words with spaces, preserving the original word order and spacing.
Approach
Straightforward Solution
A brute-force approach would iterate through the string character by character, manually reversing each word in place, which is more complex and error-prone.
Core Observation
Each word can be treated as an independent unit for reversal because the problem requires reversing characters within words but preserving word order and spacing.
Path to Optimal
Splitting the string into words using built-in methods simplifies the problem by isolating each word. Reversing each word individually and then joining them back preserves the original word order and spacing, achieving the goal cleanly and efficiently.
Optimal Approach
Use the built-in split() method to separate the string into words, reverse each word using slicing, and then join the reversed words with spaces. This approach is concise, readable, and runs in O(n) time where n is the length of the string.
Time
O(n)
Splitting the string and joining the words each take O(n) time, and reversing each word is O(k) where k is the word length; summing over all words yields O(n) total.
Space
O(n)
The auxiliary space is O(n) due to storing the list of words and the reversed words before joining; this is necessary to hold the output string.
Pattern Spotlight
String Manipulation (Word-by-Word Transformation)
When a problem requires modifying each word independently while preserving overall word order and spacing, split the string into words, transform each word separately, and then rejoin them to maintain structure.
Solution
| 1 | class Solution:
|
| 2 | def reverseWords(self, s: str) -> str:
|
| 3 | words = s.split()
|
| 4 | for i in range(len(words)):
|
| 5 | words[i] = words[i][::-1]
|
| 6 | return " ".join(words) |
Step-by-Step Solution
Split Input String into Words
| 3 | words = s.split()
|
Objective
To separate the input string into individual words for independent processing.
Key Insight
Using the built-in split() method efficiently isolates words by whitespace, enabling focused transformations on each word without worrying about spaces or word boundaries during reversal.
Interview Quick-Check
Core Logic
Splitting the string into words creates discrete units that can be reversed independently, preserving the original word order.
Common Pitfalls & Bugs
Forgetting that split() removes whitespace can lead to incorrect spacing if not handled properly during the join step.
Reverse Characters in Each Word
| 4 | for i in range(len(words)):
|
| 5 | words[i] = words[i][::-1]
|
Objective
To transform each word by reversing its characters while keeping the word's position intact.
Key Insight
Reversing each word individually using slicing is a clean and efficient way to invert characters without additional data structures or manual loops, leveraging Python's powerful string operations.
Interview Quick-Check
Core Logic
Reversing each word with slicing words[i][::-1] efficiently reverses characters in O(k) time per word.
Common Pitfalls & Bugs
Modifying the list in place ensures no extra space is used for reversed words, but care must be taken to avoid off-by-one errors in slicing.
Join Reversed Words into Final String
| 6 | return " ".join(words) |
Objective
To reconstruct the final string by concatenating reversed words with spaces, preserving original word order and spacing.
Key Insight
Joining the reversed words with a single space restores the sentence structure exactly as required, ensuring the output matches the problem's formatting constraints.
Interview Quick-Check
Core Logic
Joining with ' '.join(words) preserves the original word order and spacing, producing the correctly formatted output string.
Common Pitfalls & Bugs
Using incorrect join delimiters or forgetting to join can lead to output format errors.
Line Analysis
This solution has 1 Critical line interviewers watch for.
words[i] = words[i][::-1]Reverse the characters of the current word using slicing.
Slicing with [::-1] is a concise and efficient way to reverse strings in Python, avoiding manual character swaps or additional data structures.
words = s.split()Split the input string into a list of words separated by whitespace.
Splitting isolates each word, enabling independent reversal without manual parsing or index tracking, simplifying the problem to a word-level transformation.
return " ".join(words)Join the reversed words into a single string separated by spaces and return it.
Joining with spaces reconstructs the sentence with reversed words in original order, fulfilling the problem's output format requirements.
for i in range(len(words)):Iterate over each word index in the list.
Using a loop over indices allows in-place modification of the words list, which is memory efficient and straightforward.
Test Your Understanding
Why is it more efficient and less error-prone to split the string into words before reversing each word, rather than reversing characters in place?
Splitting isolates each word, allowing independent reversal without complex index management or in-place character swaps, simplifying the logic and reducing the chance of errors while maintaining O(n) time complexity.
Related Problems
Simulation pattern
Don't just read it. Drill it.
Reconstruct Reverse Words in a String III from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Reverse Words in a String III drill