Given an input string, reverse the string word by word.
For example,
Given s = "the sky is blue",
return "blue is sky the".
Update (2015-02-12):
For C programmers: Try to solve it in-place in O(1) space.
click to show clarification.
Clarification:
- 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.
=====================
注意,
1,被空格包围的是单词
2,输入字符串可以以空格开头或结尾,但是结果中的字符不能以空格开头或结尾
3,输出字符串中单词间的空格是一个,不能重复出现空格.
思路:
对输入字符串进行去重空格操作,
对字符串中的每个单词进行反转
对整个字符串进行反转
====
code
class Solution {
public:
void help_reverse(string &s,int start,int end){
while(start<end){///经典的反转字符串方法
swap(s[start++],s[end--]);
}
}
string removeDuplicateSpace(string s){
string res;
int b = ;
for(;b<(int)s.size();b++){
if(s[b]!= ' '){
break;
}
}///
int e = s.size() - ;
for(;e>=;e--){
if(s[e]!=' '){
break;
}
}
bool is_space = false;
for(int i = b;i<=e;i++){
if(s[i] == ' '){
if(!is_space) is_space = true;
else continue;
}else{
is_space = false;
}
res.push_back(s[i]);
}
return res;
}
void reverseWords(string &s) {
if(s.empty()) return;
s = removeDuplicateSpace(s);
int start = ;
for(size_t i = ;i<s.size();i++){
if(s[i]!=' '){
start = i;
}else{
continue;
}
size_t j = i;
while(j<s.size() && s[j]!=' '){
j++;
}
j--;
help_reverse(s,start,j);
i = j++;
}
help_reverse(s,,(int)s.size()-);
}
};