# 151. Reverse Words in a String

## Description

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.

Follow-up: If the string data type is mutable in your language, can you solve it in-place with O(1) extra space?

## Solutions

Solution 1: Use Language Built-in Functions

We split the string into a list of strings by spaces, then reverse the list, and finally join the list into a string separated by spaces.

Time complexity $O(n)$, space complexity $O(n)$, where $n$ is the length of the string.

Solution 2: Two Pointers

We can use two pointers $i$ and $j$, each time we find a word, add it to the result list, then reverse the result list, and finally join the list into a string.

Time complexity $O(n)$, space complexity $O(n)$, where $n$ is the length of the string.

• class Solution {
public String reverseWords(String s) {
List<String> words = Arrays.asList(s.trim().split("\\s+"));
Collections.reverse(words);
return String.join(" ", words);
}
}

• class Solution {
public:
string reverseWords(string s) {
int i = 0;
int j = 0;
int n = s.size();
while (i < n) {
while (i < n && s[i] == ' ') {
++i;
}
if (i < n) {
if (j != 0) {
s[j++] = ' ';
}
int k = i;
while (k < n && s[k] != ' ') {
s[j++] = s[k++];
}
reverse(s.begin() + j - (k - i), s.begin() + j);
i = k;
}
}
s.erase(s.begin() + j, s.end());
reverse(s.begin(), s.end());
return s;
}
};

• class Solution:
def reverseWords(self, s: str) -> str:
words = s.strip().split()
return ' '.join(words[::-1])

############

class Solution: # O(1) space complexity
def reverseWords(self, s: str) -> str:
# Remove leading and trailing spaces
s = s.strip()

# Reverse the entire string
s = self.reverseString(s, 0, len(s) - 1)

# Reverse each word in the string
start = 0
end = 0
while end < len(s):
if s[end] == ' ':
s = self.reverseString(s, start, end - 1)
start = end + 1
end += 1

# Reverse the last word
s = self.reverseString(s, start, end - 1)

return s

def reverseString(self, s: str, start: int, end: int) -> str:
# Convert the string to a list of characters
chars = list(s)

# Reverse the substring
while start < end:
chars[start], chars[end] = chars[end], chars[start]
start += 1
end -= 1

# Convert the list of characters back to a string
return ''.join(chars)

############

class Solution(object):
def reverseWords(self, s):
"""
:type s: str
:rtype: str
"""
return " ".join(s.split()[::-1])


• func reverseWords(s string) string {
words := strings.Split(s, " ")
var ans []string
for i := len(words) - 1; i >= 0; i-- {
if words[i] != "" {
ans = append(ans, words[i])
}
}
return strings.Join(ans, " ")
}

• function reverseWords(s: string): string {
return s.trim().split(/\s+/).reverse().join(' ');
}


• public class Solution {
public string ReverseWords(string s) {
return string.Join(" ", s.Trim().Split(" ").Where(word => !string.IsNullOrEmpty(word) && !string.IsNullOrEmpty(word.Trim())).Reverse());
}
}

• impl Solution {
pub fn reverse_words(s: String) -> String {
s.split_whitespace().rev().collect::<Vec<&str>>().join(" ")
}
}