# 151. Reverse Words in a String
Given an input string, reverse the string word by word.
Example 1:
Input: "the sky is blue"
Output: "blue is sky the"
Example 2:
Input: " hello world! "
Output: "world! hello"
Explanation: Your reversed string should not contain leading or trailing spaces.
Example 3:
Input: "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.
Note:
- A word is defined as a sequence of non-space characters.
- Input string may contain leading or trailing spaces. However, your reversed string should not contain leading or trailing spaces.
- You need to reduce multiple spaces between two words to a single space in the reversed string.
Follow up:
For C programmers, try to solve it in-place in O(1) extra space.
# Solution
Approach 1: Concatenate each word reversely.
Approach 2: In-place: first reverse the whole sentence and then reverse each word.
# Code (Python)
Approach 1:
Approach 2:
# Code (C++)
Approach 1:
// Concatenate each word reversely.
class Solution {
public:
string reverseWords(string s) {
string reversed = "";
int head = 0;
int tail = 0;
while (head < s.size() && tail <= s.size())
{
if (s[head] == ' ')
head++;
else if (tail == s.size() || s[tail] == ' ')
{
string word = s.substr(head, tail - head);
reversed = word + " " + reversed;
head = tail + 1;
}
tail++;
}
return reversed.substr(0, reversed.size() - 1);
}
};
Approach 2:
// In-place: first reverse the whole sentence and then reverse each word.
class Solution {
private:
void reverseString(string& s, int head, int tail) {
while (head < tail)
{
std::swap(s[head], s[tail]);
head++;
tail--;
}
}
public:
string reverseWords(string s) {
// Reverse the while sentence.
reverseString(s, 0, s.size() - 1);
// Reverse each word.
int head = 0;
int tail = 0;
while (head < s.size() && tail <= s.size())
{
if (s[head] == ' ')
head++;
else if (tail == s.size() || s[tail] == ' ')
{
reverseString(s, head, tail - 1);
head = tail + 1;
}
tail++;
}
// Remove duplicated zeros.
head = 0;
tail = 0;
while (tail < s.size())
{
if (s[tail] != ' ')
{
s[head] = s[tail];
head++;
}
else if (tail > 0 && s[tail-1] != ' ')
{
s[head] = ' ';
head++;
}
tail++;
}
if (head > 0 && s.size() > 0 && s[s.size()-1] == ' ')
head--;
return s.substr(0, head);
}
};