# Reverse Words in a String III
**Difficulty:** EASY
[External](https://leetcode.com/problems/reverse-words-in-a-string-iii)
Canonical: https://scaleengineer.com/dsa/problems/reverse-words-in-a-string-iii
**Patterns:** [Two Pointers](https://scaleengineer.com/dsa/patterns/two-pointers)
**Data structures:** String
**Companies:** [BNY Mellon](https://scaleengineer.com/companies/bny-mellon), [Walmart Labs](https://scaleengineer.com/companies/walmart-labs), [Wissen Technology](https://scaleengineer.com/companies/wissen-technology), [Yandex](https://scaleengineer.com/companies/yandex), [Salesforce](https://scaleengineer.com/companies/salesforce), [Devtron](https://scaleengineer.com/companies/devtron)
---
## Problem
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 = "Mr Ding"
**Output:** "rM gniD"

**Constraints:**

* `1 <= s.length <= 5 * 104`
* `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.

# Approaches
## Using Split, Reverse, and Join
This approach is straightforward and relies on built-in language features. The idea is to first break the sentence down into its constituent words, handle each word individually, and then piece the sentence back together.
**Time:** O(N), where N is the length of the input string. The `split()` operation takes O(N) time. Reversing each word and building the new string also takes O(N) time in total, as each character is processed a constant number of times. · **Space:** O(N), where N is the length of the input string. This space is used to store the array of words created by `split()` and the `StringBuilder` for the result. In the worst case, the array of words can take up O(N) space.
**Pros:** Simple to implement and easy to understand due to the high-level abstractions used.; Code is often more concise and readable.
**Cons:** Creates several intermediate data structures, such as an array of strings for the words and a new `StringBuilder` for each word, leading to higher memory consumption.; The overhead of splitting the string and creating multiple new objects can be less performant than in-place manipulation, especially for very long strings.
### Explanation
In this method, we first use the `split()` function to divide the input string `s` into an array of words, using the space character as a delimiter. This gives us a clean list of all the words.

Next, we iterate over this array. For each word, we can use a `StringBuilder` to easily reverse the characters. We create a `StringBuilder` with the current word, call its `reverse()` method, and then append this reversed word to a main `StringBuilder` that will hold our final result.

To preserve the original sentence structure, we also append a space after each reversed word, except for the very last one. Finally, we convert the main `StringBuilder` back to a string to get our desired output.

```java
class Solution {
    public String reverseWords(String s) {
        String[] words = s.split(" ");
        StringBuilder result = new StringBuilder();
        for (int i = 0; i < words.length; i++) {
            String word = words[i];
            StringBuilder reversedWord = new StringBuilder(word);
            reversedWord.reverse();
            result.append(reversedWord);
            if (i < words.length - 1) {
                result.append(" ");
            }
        }
        return result.toString();
    }
}
```
### Algorithm
- Split the input string `s` by the space character (`' '`) to create an array of strings, where each element is a word.
- Initialize an empty `StringBuilder` called `result` to build the output string.
- Iterate through the `words` array.
- For each `word`, create a new `StringBuilder` from it, call the `reverse()` method, and append the reversed word to the `result`.
- After appending a reversed word, check if it's not the last word in the array. If it's not, append a space to the `result` to maintain the separation between words.
- After the loop completes, convert the `result` `StringBuilder` to a string and return it.

## Two Pointers Approach
This is a more optimized approach that modifies a character array representation of the string in-place. It avoids the overhead of creating an array of separate string objects, making it more efficient in terms of memory and speed.
**Time:** O(N), where N is the length of the string. We iterate through the character array once to find the words, and the reversal process ensures that each character is swapped at most once. Therefore, each character is touched a constant number of times. · **Space:** O(N), where N is the length of the string. In Java, strings are immutable, so a character array of size N is required to perform the modifications. This is the auxiliary space needed.
**Pros:** More efficient in terms of memory as it avoids creating an intermediate array of strings.; Generally faster as it reduces object creation overhead and relies on direct array manipulation.
**Cons:** The logic is slightly more complex than the split-and-join method, requiring manual tracking of word boundaries.; Requires a helper function for the in-place reversal, which adds a bit more code.
### Explanation
Instead of splitting the string into an array of words, this method works on a single mutable sequence of characters. First, we convert the input string into a character array.

We then use two pointers to walk through this array. A `start` pointer keeps track of the beginning of the current word, and an `end` pointer scans forward to find the end of that word. A word ends when we encounter a space or reach the end of the entire string.

Once a word is identified (from `start` to `end - 1`), we call a helper function to reverse that specific segment of the character array. This reversal is done in-place, by swapping characters from the outer edges of the word towards the center. After a word is reversed, we update the `start` pointer to the position right after the space, and the process continues for the next word.

After iterating through the entire array, all words will have been reversed in place. The final step is to convert the modified character array back into a string.

```java
class Solution {
    public String reverseWords(String s) {
        char[] chars = s.toCharArray();
        int start = 0;
        for (int end = 0; end <= chars.length; end++) {
            if (end == chars.length || chars[end] == ' ') {
                // Found a word from start to end - 1
                reverse(chars, start, end - 1);
                // Move start to the beginning of the next word
                start = end + 1;
            }
        }
        return new String(chars);
    }

    private void reverse(char[] arr, int left, int right) {
        while (left < right) {
            char temp = arr[left];
            arr[left] = arr[right];
            arr[right] = temp;
            left++;
            right--;
        }
    }
}
```
### Algorithm
- Convert the input string `s` into a character array `chars` to allow for in-place modification.
- Initialize a pointer `start = 0` to mark the beginning of the current word.
- Iterate through the `chars` array with a pointer `end` from `0` to `s.length()`.
- When `chars[end]` is a space or `end` reaches the end of the string, we have found a word boundary. The word is located from index `start` to `end - 1`.
- Call a helper function to reverse the characters in the `chars` array between the `start` and `end - 1` indices.
- After reversing, update `start` to `end + 1` to set the beginning of the next word.
- Once the loop is complete, convert the modified `chars` array back into a string and return it.

# Solutions
### Java

```java
class Solution {
public
  String reverseWords(String s) {
    StringBuilder res = new StringBuilder();
    for (String t : s.split(" ")) {
      for (int i = t.length() - 1; i >= 0; --i) {
        res.append(t.charAt(i));
      }
      res.append(" ");
    }
    return res.substring(0, res.length() - 1);
  }
}

```

### JavaScript

```javascript
/** * @param {string} s * @return {string} */ var reverseWords = function (s) {
  return s
    .split(" ")
    .map((t) => t.split("").reverse().join(""))
    .join(" ");
};

```

### CPP

```cpp
class Solution {
public:
  string reverseWords(string s) {
    for (int i = 0, n = s.size(); i < n; ++i) {
      int j = i;
      while (++j < n && s[j] != ' ')
        ;
      reverse(s.begin() + i, s.begin() + j);
      i = j;
    }
    return s;
  }
};

```

### Python

```python
class Solution : def reverseWords ( self , s : str ) -> str : return ' ' . join ([ t [:: - 1 ] for t in s . split ( ' ' )])
```