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" Explanation: Your reversed string should not contain leading or trailing spaces.
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
.
Reverse Words in a String Solutions
✅Time: O(n)
✅Space: O(n)
C++
class Solution {
public:
string reverseWords(string s) {
reverse(begin(s), end(s)); // reverse the whole string
reverseWords(s, s.length()); // reverse each word
return cleanSpaces(s, s.length()); // clean up spaces
}
private:
void reverseWords(string& s, int n) {
int i = 0;
int j = 0;
while (i < n) {
while (i < j || i < n && s[i] == ' ') // skip spaces
++i;
while (j < i || j < n && s[j] != ' ') // skip non spaces
++j;
reverse(begin(s) + i, begin(s) + j); // reverse the word
}
}
// trim leading, trailing, and middle spaces
string cleanSpaces(string& s, int n) {
int i = 0;
int j = 0;
while (j < n) {
while (j < n && s[j] == ' ') // skip spaces
++j;
while (j < n && s[j] != ' ') // keep non spaces
s[i++] = s[j++];
while (j < n && s[j] == ' ') // skip spaces
++j;
if (j < n) // keep only one space
s[i++] = ' ';
}
return s.substr(0, i);
}
};
Java
class Solution {
public String reverseWords(String s) {
StringBuilder sb = new StringBuilder(s).reverse(); // reverse the whole string
reverseWords(sb, sb.length()); // reverse each word
return cleanSpaces(sb, sb.length()); // clean up spaces
}
private void reverseWords(StringBuilder sb, int n) {
int i = 0;
int j = 0;
while (i < n) {
while (i < j || i < n && sb.charAt(i) == ' ') // skip spaces
++i;
while (j < i || j < n && sb.charAt(j) != ' ') // skip non spaces
++j;
reverse(sb, i, j - 1); // reverse the word
}
}
// trim leading, trailing, and middle spaces
private String cleanSpaces(StringBuilder sb, int n) {
int i = 0;
int j = 0;
while (j < n) {
while (j < n && sb.charAt(j) == ' ') // skip spaces
++j;
while (j < n && sb.charAt(j) != ' ') // keep non spaces
sb.setCharAt(i++, sb.charAt(j++));
while (j < n && sb.charAt(j) == ' ') // skip spaces
++j;
if (j < n) // keep only one space
sb.setCharAt(i++, ' ');
}
return sb.substring(0, i).toString();
}
private void reverse(StringBuilder sb, int l, int r) {
while (l < r) {
final char temp = sb.charAt(l);
sb.setCharAt(l++, sb.charAt(r));
sb.setCharAt(r--, temp);
}
}
}
Python
class Solution:
def reverseWords(self, s: str) -> str:
return ' '.join(reversed(s.split()))
Watch Tutorial
Checkout more Solutions here