## Algorithm

Problem Name: 151. Reverse Words in a String

Given an input string `s`, reverse the order of the words.

A word is defined as a sequence of non-space characters. The words in `s` will be separated by at least one space.

Return a string of the words in reverse order concatenated by a single space.

Note that `s` may contain leading or trailing spaces or multiple spaces between two words. The returned string should only have a single space separating the words. Do not include any extra spaces.

Example 1:

```Input: s = "the sky is blue"
Output: "blue is sky the"
```

Example 2:

```Input: s = "  hello world  "
Output: "world hello"
```

Example 3:

```Input: s = "a good   example"
Output: "example good a"
Explanation: You need to reduce multiple spaces between two words to a single space in the reversed string.
```

Constraints:

• `1 <= s.length <= 104`
• `s` contains English letters (upper-case and lower-case), digits, and spaces `' '`.
• There is at least one word in `s`.

## Code Examples

### #1 Code Example with C Programming

```Code - C Programming```

``````
void reverse(char *start, char *end) {
char c;
while (start  <  end) {
c = *start;
*start = *end;
*end = c;
start ++;
end --;
}
}
void reverseWords(char *s) {
int len;
char *p1, *p2;

if (!s || !*s) return;

len = strlen(s);

while (len && *(s + len - 1) == ' ') {  // skip trailing spaces
*(s + len - 1) = 0;
len --;
}

reverse(s, s + len - 1);

p1 = s;
p2 = p1 + 1;
while (*p1 != 0) {
while (*p2 != 0 && *p2 != ' ') p2 ++;   // find the end of a word
reverse(p1, p2 - 1);                // reverse the word
p1 = p2;

while (*(p1 - 1) == ' ') p1 --;      // there might be muliple spaces after above reverse

while (*p2 == ' ') p2 ++;               // skip multiple spaces
if (*p2 == 0) *p1 = 0;
else p1 ++;                         // leave one space
}
}
``````
Copy The Code &

Input

cmd
s = "the sky is blue"

Output

cmd
"blue is sky the"

### #2 Code Example with C++ Programming

```Code - C++ Programming```

``````
class Solution {
public:
void reverseWords(string &s) {
// Reverse string
reverse(s.begin(), s.end());
// Reverse every word
int i = 0, j = 0;
while(i != s.size()){
while(j  <  s.size() && s[j] != ' ') j++;
reverse(s.begin() + i, s.begin() + j);
i = j;
while(i  <  s.size() && s[i] == ' ') i++, j++;
}
// Remove extra ' '
i = 0, j = 0;
while(j  <  s.size()){
bool new_word = false;
while(j < s.size() && s[j] == ' '){
new_word = true;
j++;
}
if(j == s.size()) break;
if(new_word && i > 0) s[i++] = ' ';
s[i++] = s[j++];
}
s = s.substr(0, i);
}
};

// O(n) space.
class Solution {
public:
void reverseWords(string &s) {
string res = "";
string word = "";
int j = 0;
for(int i = 0; i < s.size(); i++){
while(s[i] == ' ') i++;
j = i;
while(s[j] != ' ') j++;
word = s.substr(i, j - i);
if(res != "" && word != ""> word += " ";
res = word + res;
i = j;
}
s = res;
}
};
``````
Copy The Code &

Input

cmd
s = "the sky is blue"

Output

cmd
"blue is sky the"

### #3 Code Example with Java Programming

```Code - Java Programming```

``````
class Solution {
public String reverseWords(String s) {
StringBuilder result = new StringBuilder();
int idx = s.length() - 1;
while (idx >= 0) {
if (s.charAt(idx) == ' ') {
idx--;
continue;
}
StringBuilder sb = new StringBuilder();
while (idx >= 0 && Character.isLetterOrDigit(s.charAt(idx))) {
sb.append(s.charAt(idx--));
}
result.append(sb.reverse().toString()).append(" ");
}
return result.toString().trim();
}
}
``````
Copy The Code &

Input

cmd
s = " hello world "

Output

cmd
"world hello"

### #4 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const reverseWords = function(str) {
return str
.trim()
.split(/\s+/)
.reverse()
.join(" ");
};
``````
Copy The Code &

Input

cmd
s = " hello world "

Output

cmd
"world hello"

### #5 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def reverseWords(self, s: str) -> str:
return " ".join(s.split()[::-1])
``````
Copy The Code &

Input

cmd
s = "a good example"

Output

cmd
"example good a"

### #6 Code Example with C# Programming

```Code - C# Programming```

``````
using System;
using System.Linq;

namespace LeetCode
{
public class _0151_ReverseWordsInAString
{
public string ReverseWords(string s) {
if (string.IsNullOrWhiteSpace(s)) return string.Empty;

return string.Join(" ", s.Split(new char[] { ' ' }, StringSplitOptions.RemoveEmptyEntries).Reverse());
}
}
}
``````
Copy The Code &

Input

cmd
s = "a good example"

Output

cmd
"example good a"