#557

Easy

auto_awesomeTwo-pointer scanning with invariant tracking

LeetCode Problem Workspace

Reverse Words in a String III

Reverse Words in a String III involves reversing each word in a sentence using the two-pointer technique.

Problem Statement

Given a string s, you are tasked with reversing the characters of each word in the sentence while keeping the overall word order intact. The string contains printable ASCII characters with at least one word and no leading or trailing spaces. Words are separated by a single space.

For example, given the input 'Let's take LeetCode contest', the output should be 's'teL ekat edoCteeL tsetnoc'. You must preserve whitespace and word positions while applying the reversal to individual words using an efficient algorithm.

Examples

Example 1

Input: s = "Let's take LeetCode contest"

Output: "s'teL ekat edoCteeL tsetnoc"

Example details omitted.

Example 2

Input: s = "Mr Ding"

Output: "rM gniD"

Example details omitted.

Constraints

1 <= s.length <= 5 * 104
s contains printable ASCII characters.
s does not contain any leading or trailing spaces.
There is at least one word in s.
All the words in s are separated by a single space.

Solution Approach

Two-Pointer Technique

Utilize two pointers: one to mark the beginning and one to mark the end of each word. Reverse the word in place by adjusting these pointers to swap characters.

In-place Reversal

Perform the reversal without allocating extra space for another array. You can directly modify the input string by swapping characters using the two-pointer approach.

Iterate Over Words

Iterate over the string word by word, using the two-pointer technique on each word. Keep track of word boundaries by identifying spaces, ensuring that only the words are reversed.

Complexity Analysis

Metric	Value
Time	\mathcal{O}(N)
Space	\mathcal{O}(1)

The time complexity is O(N), where N is the length of the string, because we traverse the string once. The space complexity is O(1) as we reverse the string in place without using extra space.

What Interviewers Usually Probe

Look for understanding of two-pointer techniques and their application in string manipulation.
Evaluate the candidate's ability to optimize space usage with in-place operations.
Test for edge case handling, such as a single-word string or a string with multiple spaces.

Common Pitfalls or Variants

Common pitfalls

Misidentifying word boundaries and reversing characters across spaces.
Not handling strings with a single word or very short input correctly.
Forgetting to manage the space complexity by using in-place modification.

Follow-up variants

Handle strings with multiple spaces between words or trailing spaces.
Implement the solution with a different space-time trade-off (e.g., using a stack).
Expand the problem to reverse a sentence as a whole while reversing words.

FAQ

How can I reverse words in a string efficiently?

Use the two-pointer technique to reverse each word in place without extra space.

What is the time complexity of reversing words in a string?

The time complexity is O(N), where N is the length of the string, as we only traverse the string once.

What if the string contains multiple spaces between words?

Ensure you handle word boundaries by checking spaces between words, ensuring each word is reversed correctly.

Why is the space complexity O(1)?

We reverse the words in place, without using any additional space beyond the input string.

What is the two-pointer approach in this problem?

The two-pointer approach uses one pointer to mark the beginning and another for the end of a word. By swapping characters, the word is reversed in place.

terminal

Solution

Solution 1: Simulation

We can split the string $\textit{s}$ into an array of words $\textit{words}$ by spaces, then reverse each word and concatenate them back into a string.

1

2

3

class Solution:
    def reverseWords(self, s: str) -> str:
        return " ".join(t[::-1] for t in s.split())

Continue Practicing

#556 next greater element iii #567 permutation in string #541 reverse string ii