Reverse Words in a String III

easyLeetCode #557
two-pointers

Description

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

Example 1:
Input: s = "Let's take LeetCode contest"
Output: "s'teL ekat edoCteeL tsetnoc"
Explanation: Each word is reversed individually:
"Let's" -> "s'teL"
"take" -> "ekat"
"LeetCode" -> "edoCteeL"
"contest" -> "tsetnoc"

Example 2:
Input: s = "Mr Ding"
Output: "rM gniD"
Explanation: "Mr" -> "rM", "Ding" -> "gniD"

Constraints

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

Signature

def solution(s: str) -> str: ...

Complexity
  • Time: O(n)
  • Space: O(n)

Hints
Pattern
Two pointers to reverse each word in place
Approach
Split by spaces or track word start/end indices. For each word, use two pointers to reverse characters.
Complexity
Find word boundaries, then reverse characters within each word

Solutions

def solution(s):
    results = list(s)

    left = 0
    right = 0
    for right in range(len(results)):
        if results[right] == " ":
            i, j = left, right - 1
            while i < j:
                results[i], results[j] = results[j], results[i]
                i += 1
                j -= 1
            left = right + 1

    i, j = left, right
    while i < j:
        results[i], results[j] = results[j], results[i]
        i += 1
        j -= 1

    return "".join(results)