algoadvance

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"

Example 2:

Input: s = "God Ding"
Output: "doG 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 the words in s are separated by a single space.

Clarifying Questions

1. Can the input string contain punctuation or special characters within the words?
   • Yes, the input can contain any printable ASCII characters.
2. Are multiple consecutive spaces allowed?
   • No, all the words are separated by a single space and there are no leading or trailing spaces.

Strategy

1. Split the input string s into words based on spaces.
2. Reverse each word individually.
3. Join the reversed words back together with a space separator.
4. Return the resulting string.

Code

def reverseWords(s: str) -> str:
    # Split the string into words
    words = s.split()
    # Reverse each word and store the results back
    reversed_words = [word[::-1] for word in words]
    # Join the reversed words with space separator
    return ' '.join(reversed_words)

# Testing the function with the provided examples
print(reverseWords("Let's take LeetCode contest"))   # "s'teL ekat edoCteeL tsetnoc"
print(reverseWords("God Ding"))                      # "doG gniD"

Time Complexity

• Splitting the string into words: O(n) where n is the length of the string since we traverse each character to split the words.
• Reversing each word: Each word is reversed in O(m) where m is the length of the word. Summed over all words, this still results in O(n).
• Joining the words: This operation involves traversing all characters to create the new string, which is O(n).

Thus, the overall time complexity is O(n), where n is the length of the input string s. This algorithm efficiently handles the provided constraints and should perform well within the given limits.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?