Given an input string, reverse the string word by word.
For example,
Given s = "the sky is blue",
return "blue is sky the".
- What constitutes a word?
A sequence of non-space characters constitutes a word. - Could the input string contain leading or trailing spaces?
Yes. However, your reversed string should not contain leading or trailing spaces. - How about multiple spaces between two words?
Reduce them to a single space in the reversed string.
We can achieve this by reverse each word first and then reverse the whole string. Here is a example:
string: "the sky is blue"
Reverse each word: "eht yks si eulb"
Reverse the whole string: "blue is sky the"
C++ Code:
/*
* func: reverse_words
* goal: reverse the string word by word
* @param s: input string s
* return:
*/
/*
* reverse each word first and then reverse the whole string
* complexity: time O(n), space O(n)
*/
void reverse_words(string &s){
string word = "";
string intermediate = "";
for(const char &ch : s){
if(ch == ' '){
if(word.length() > 0){
reverse(word.begin(), word.end());
intermediate += word + " ";
}
word.clear();
}else{
word += ch;
}
}
if(word.length() > 0){
reverse(word.begin(), word.end());
intermediate += word;
}else{
size_t space = intermediate.find_last_of(" ");
if(space != string::npos)
intermediate.erase(space);
}
//Reverse the whole string
reverse(intermediate.begin(), intermediate.end());
s = intermediate;
}
Python Code:
# func: reverse words in the string
# @param s: input string
# @return: reversed string
def reverse_words(s):
words = s.split(" ")
intermediate = ""
for word in words:
if word:
intermediate += word[::-1] + ' '
return intermediate[-2::-1]
