LeetCode Daily Challenges: 557. Reverse Words in a String III

 557. Reverse Words in a String III

Problem 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"

Example 2:

Input: s = "God Ding"

Output: "doG gniD"

Intuition

The problem requires us to reverse the order of characters in each word within a sentence while preserving whitespace and the initial word order. To achieve this, we can split the sentence into words, reverse each word individually, and then join them back together with whitespace to form the reversed sentence.

Approach

1. Split the input sentence into words: We can split the sentence into words using whitespace as the delimiter, which will give us an array of words.
2. Reverse each word: For each word in the array, we reverse its characters. We can use a StringBuilder to efficiently reverse the characters of a word.
3. Join the reversed words: Finally, we join the reversed words back together with whitespace to form the reversed sentence.

Complexity

1. Time complexity: The time complexity is determined by the length of the input sentence and the number of words it contains. Let's denote the length of the input sentence as n and the average word length as k. Splitting the sentence takes O(n) time, and reversing each word takes O(k) time, so the overall time complexity is O(n * k).
2. Space complexity: The space complexity depends on the storage required for the array of words and the reversed sentence. Since we are not using any additional data structures apart from the input and output, the space complexity is O(n), where n is the length of the input sentence.

Code Snapshots: