Code Implementation

class Solution:
    def reverseWords(self, s: str) -> str:
        # Split the string into words, reverse each word, then join back
        return ' '.join(word[::-1] for word in s.split())
      

class Solution {
public:
    string reverseWords(string s) {
        stringstream ss(s);
        string word, res;
        while (ss >> word) {
            reverse(word.begin(), word.end());
            if (!res.empty()) res += " ";
            res += word;
        }
        return res;
    }
};
      

class Solution {
    public String reverseWords(String s) {
        String[] words = s.split(" ");
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < words.length; i++) {
            sb.append(new StringBuilder(words[i]).reverse());
            if (i != words.length - 1) sb.append(" ");
        }
        return sb.toString();
    }
}
      

var reverseWords = function(s) {
    return s.split(' ')
            .map(word => word.split('').reverse().join(''))
            .join(' ');
};
      

Problem Description

Given a string s containing words separated by single spaces, reverse the characters of each word in the string while preserving the order of the words and spaces. Each word consists of non-space characters only. The output should be a new string where every word is reversed, but the sequence of words and spaces remains unchanged.

• There is exactly one valid output for each input.
• You must not rearrange the words or remove/add spaces.
• All words are separated by a single space.

Example: If s = "Let's take LeetCode contest", the output should be "s'teL ekat edoCteeL tsetnoc".

Thought Process

To solve this problem, first consider the brute-force approach: for each word in the string, reverse its characters, then put the words back together in their original order. The key is to identify and process words one at a time, ensuring spaces are preserved between them.

One way is to split the string by spaces, reverse each word, and then join them back with single spaces. This method is simple and leverages built-in string and array operations. Alternatively, we could manually scan the string, reverse characters between spaces, and build the output step by step, but this is more complex and error-prone.

The optimized approach makes use of language features (like split and reverse) to write concise and efficient code, avoiding unnecessary loops or manual handling of spaces.

Solution Approach

The solution can be broken down into the following steps:

1. Split the String:
   • Use the language's split function to divide the string s into a list/array of words, using the space character as the separator.
2. Reverse Each Word:
   • Iterate over the list of words, and for each word, reverse its characters. This can be done using slicing (Python), built-in reverse() (C++), or StringBuilder.reverse() (Java).
3. Rejoin the Words:
   • After reversing all words, join them back together with a single space between each word to form the final string.

This approach is efficient because splitting and joining strings, as well as reversing characters, are all operations with linear time complexity relative to the length of the input.

Example Walkthrough

Let's walk through the input s = "Let's take LeetCode contest" step by step:

1. Split: The string is split into words:
   • ["Let's", "take", "LeetCode", "contest"]
2. Reverse Each Word:
   • "Let's" becomes "s'teL"
   • "take" becomes "ekat"
   • "LeetCode" becomes "edoCteeL"
   • "contest" becomes "tsetnoc"
3. Join: The reversed words are joined with spaces:
   • "s'teL ekat edoCteeL tsetnoc"

The output matches the expected result.

Time and Space Complexity

• Brute-force Approach:
  • If you manually scan the string and reverse each word by moving characters, both time and space complexity are O(n), where n is the length of the string.
• Optimized Approach:
  • Splitting the string, reversing each word, and joining them all take O(n) time in total.
  • Space complexity is also O(n) due to the storage of the list of words and the final output string.

In all reasonable approaches, both time and space complexity are linear in the size of the input.

Summary

The problem asks us to reverse each word in a string while keeping the words and spaces in their original order. By splitting the string into words, reversing each word, and joining them back, we achieve an elegant and efficient solution. This method leverages built-in language features for clarity and speed, making the code both concise and easy to understand.