LeetCode 557 - Reverse Words in a String III

Difficulty: 🟢 Easy
Topics: Two Pointers, String

Solution

Problem Understanding

The problem requires reversing the characters of each individual word in a string while maintaining the original order of the words and the spacing between them. In other words, the sentence structure remains the same, but each word is mirrored in place. For example, the word "Let's" becomes "s'teL", and "LeetCode" becomes "edoCteeL".

The input s is a string that contains only printable ASCII characters, and it is guaranteed to have no leading or trailing spaces. All words are separated by a single space. The string length can go up to 50,000 characters, so solutions must handle relatively large strings efficiently.

Important edge cases include strings with a single word, strings with very long words, or strings where words contain punctuation. The problem guarantees at least one word, so empty input does not need to be handled.

Approaches

The brute-force approach is to split the string into words using the space as a delimiter, reverse each word individually, and then join them back into a single string. This approach works correctly because it processes each word independently and maintains the original word order. However, it may create unnecessary intermediate lists of strings and may not be optimal in terms of memory if the string is very long.

The optimal approach leverages a two-pointer technique to reverse characters in-place within each word. By iterating through the string once and using indices to mark word boundaries, we can reverse the characters in each word without allocating extra memory for intermediate lists. This reduces the additional memory overhead and can slightly improve performance on very large inputs.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n)	O(n)	Split string into words, reverse each word, join back
Optimal	O(n)	O(n)	Iterate with two pointers, reverse words in-place within a list of characters

Algorithm Walkthrough

Convert the input string s into a mutable list of characters. This is necessary because strings in most languages, including Python, are immutable.
Initialize a pointer start at 0 to mark the beginning of the current word.
Iterate through the characters of the string with an index end. When a space is encountered or the end of the string is reached, treat this as the end of the current word.
Reverse the characters between start and end - 1. This step uses a standard two-pointer swap to mirror the word.
Move the start pointer to end + 1 to begin the next word.
After iterating through all characters and reversing all words, convert the list of characters back into a string and return it.

Why it works: The algorithm maintains the invariant that the order of words is preserved, and each word is reversed individually. By using a two-pointer reversal within each word boundary, the algorithm ensures all characters in a word are reversed exactly once.

Python Solution

class Solution:
    def reverseWords(self, s: str) -> str:
        chars = list(s)
        start = 0
        n = len(chars)
        
        for end in range(n + 1):
            if end == n or chars[end] == ' ':
                left, right = start, end - 1
                while left < right:
                    chars[left], chars[right] = chars[right], chars[left]
                    left += 1
                    right -= 1
                start = end + 1
        
        return ''.join(chars)

The Python implementation first converts the string into a list of characters so it can modify individual characters. It iterates over the indices of the list and reverses each word using two pointers left and right. After processing all words, it joins the character list back into a string and returns it.

Go Solution

func reverseWords(s string) string {
    chars := []rune(s)
    start := 0
    n := len(chars)
    
    for end := 0; end <= n; end++ {
        if end == n || chars[end] == ' ' {
            left, right := start, end-1
            for left < right {
                chars[left], chars[right] = chars[right], chars[left]
                left++
                right--
            }
            start = end + 1
        }
    }
    
    return string(chars)
}

The Go implementation is similar to Python but uses a slice of rune instead of a string to handle mutable characters. The two-pointer reversal is applied the same way. Converting back to a string at the end ensures the function returns the correct result.

Worked Examples

Example 1: s = "Let's take LeetCode contest"

Step	start	end	Current word	Reversed word	chars
Initial	0	0	-	-	['L','e','t',"'",'s',' ','t','a','k','e',' ','L','e','e','t','C','o','d','e',' ','c','o','n','t','e','s','t']
Word 1	0	5	"Let's"	"s'teL"	['s',''','t','e','L',' ','t','a','k','e',' ','L','e','e','t','C','o','d','e',' ','c','o','n','t','e','s','t']
Word 2	6	10	"take"	"ekat"	['s',''','t','e','L',' ','e','k','a','t',' ','L','e','e','t','C','o','d','e',' ','c','o','n','t','e','s','t']
Word 3	11	19	"LeetCode"	"edoCteeL"	['s',''','t','e','L',' ','e','k','a','t',' ','e','d','o','C','t','e','e','L',' ','c','o','n','t','e','s','t']
Word 4	20	27	"contest"	"tsetnoc"	['s',''','t','e','L',' ','e','k','a','t',' ','e','d','o','C','t','e','e','L',' ','t','s','e','t','n','o','c']

Final output: "s'teL ekat edoCteeL tsetnoc"

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each character is visited once during iteration and potentially once more during word reversal.
Space	O(n)	The input string is converted into a list of characters, which requires O(n) extra space.

The algorithm is linear because both the iteration and the in-place reversal of words are O(n) operations. Space usage is dominated by the mutable character array.

Test Cases

# test cases
assert Solution().reverseWords("Let's take LeetCode contest") == "s'teL ekat edoCteeL tsetnoc"  # standard example
assert Solution().reverseWords("Mr Ding") == "rM gniD"  # two-word input
assert Solution().reverseWords("hello") == "olleh"  # single word
assert Solution().reverseWords("a b c d") == "a b c d"  # single-character words
assert Solution().reverseWords("Python3 is fun!") == "3nohtyP si !nuf"  # punctuation included
assert Solution().reverseWords("longword" * 5000) == ("drowgnol" * 5000)  # stress test for large input

Test	Why
"Let's take LeetCode contest"	Standard multiple-word example
"Mr Ding"	Simple two-word test
"hello"	Single-word edge case
"a b c d"	Single-character words to check minimal word reversal
"Python3 is fun!"	Words with punctuation and numbers
Large repeated word	Stress test for performance on max input size

Edge Cases

One important edge case is a single-word string. A naive implementation that expects spaces may fail to reverse the only word. Our algorithm handles this correctly because it checks for the end of the string as a word boundary.

Another edge case is words that contain punctuation or numbers. Since the reversal logic only operates on character positions and does not filter content, punctuation and digits are reversed along with letters, preserving correctness.

A third edge case is very long strings, especially near the maximum length of 50,000 characters. A solution that repeatedly creates new strings would be inefficient. The in-place character array approach ensures that the solution remains linear in time and does not create multiple intermediate strings, handling large inputs efficiently.