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" 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 <= 104scontains 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
}
}
Input
Output
#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;
}
};
Input
Output
#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();
}
}
Input
Output
#4 Code Example with Javascript Programming
Code -
Javascript Programming
const reverseWords = function(str) {
return str
.trim()
.split(/\s+/)
.reverse()
.join(" ");
};
Input
Output
#5 Code Example with Python Programming
Code -
Python Programming
class Solution:
def reverseWords(self, s: str) -> str:
return " ".join(s.split()[::-1])
Input
Output
#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());
}
}
}
Input
Output