Reverse Words in a String III

Difficulty: Easy | Acceptance: 84.00% | Paid: No Topics: Two Pointers, String

Given a string s, reverse the order of characters in each word within a sentence while still preserving whitespace and initial word order.

• Examples
• Constraints
• Approach 1: Built-in Functions
• Approach 2: Two Pointers
• Approach 3: Stack

Examples

Example 1:

Input: s = "Let's take LeetCode contest"
Output: "s'teL ekat edoCteeL tsetnoc"

Example 2:

Input: s = "God Ding"
Output: "doG gniD"

Constraints

1 <= s.length <= 5 * 10⁴
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.

Approach 1: Built-in Functions

Intuition Utilize the standard library functions to split the string into words, reverse each word individually, and then join them back together.

Steps

• Split the input string by spaces to get an array of words.
• Iterate through the array and reverse each word.
• Join the reversed words back into a single string with spaces.

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

Complexity

• Time: O(N), where N is the length of the string. We iterate through the string to split and join, and reversing each word takes linear time relative to the word length.
• Space: O(N), to store the array of words and the resulting string.
• Notes: This approach is concise and leverages built-in methods effectively.

Approach 2: Two Pointers

Intuition Convert the string into a mutable character array. Use two pointers to identify the start and end of each word, then reverse the characters in place between these pointers.

Steps

• Convert the string to a character array (if necessary for the language).
• Initialize a pointer left at the start of the string.
• Iterate through the string with a pointer right.
• When right encounters a space or the end of the string, reverse the characters from left to right - 1.
• Update left to right + 1 to start the next word.
• Convert the character array back to a string and return it.

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

Complexity

• Time: O(N), we traverse the string once and each character is swapped at most once.
• Space: O(N) for the character array (or O(1) if the language allows in-place string modification like C++).
• Notes: This approach avoids creating many intermediate string objects, which can be more efficient in memory-managed languages.

Approach 3: Stack

Intuition Use a stack to reverse the characters of each word. Push characters onto the stack until a space is encountered, then pop them to build the reversed word.

Steps

• Initialize an empty stack and a result list/string.
• Iterate through each character in the string.
• If the character is not a space, push it onto the stack.
• If the character is a space, pop all characters from the stack and append them to the result, then append the space.
• After the loop, pop any remaining characters from the stack for the last word.
• Return the result string.

class Solution:
    def reverseWords(self, s: str) -> str:
        stack = []
        res = []
        for char in s:
            if char != " ":
                stack.append(char)
            else:
                while stack:
                    res.append(stack.pop())
                res.append(" ")
        while stack:
            res.append(stack.pop())
        return "".join(res)

Complexity

• Time: O(N), each character is pushed and popped exactly once.
• Space: O(N), for the stack and the result string.
• Notes: This approach demonstrates the use of a stack data structure for reversal but is generally less space-efficient than the two-pointer approach due to the auxiliary stack storage.