557. Reverse Words in a String III
最简单的把空白之间的词反转
class Solution {
public:
string reverseWords(string s) {
vector<int> blank;
for(int i = ;i < s.size();i++){
if(s[i] == ' ')
blank.push_back(i);
}
int start = ;
int end;
for(int i = ;i < blank.size();i++){
end = blank[i] - ;
reverse(s,start,end);
start = end + ;
}
reverse(s,start,s.size() - );
return s;
}
void reverse(string& s,int start,int end){
while(start < end){
char tmp = s[end];
s[end] = s[start];
s[start] = tmp;
start++;
end--;
}
return;
}
};
151. Reverse Words in a String
151题实际上比557题要难一些。难在,字符串中的空格不再仅仅在字符之间,在字符串的开头和结尾都可能有,并且空格的个数不再仅仅是1,而是有可能有许多。
输出的要求则是只能是字符+一个空格作为中间的间隔。
思路:先把整个字符串reverse,然后找每个子字符串第一个字符和最后一个,遇到空格都跳过,然后把这些子字符串reverse并+一个空格,最后一个处理的时候,我有点不知道怎么处理多出的末尾
的空格, 就用了一种暴力的方法
class Solution {
public:
string reverseWords(string s) {
if(s.empty())
return "";
string res = "";
reverse(s,,s.size() - );
for(int i = ;i < s.size();i++){
if(s[i] != ' '){
int j = i;
while(s[j] != ' ' && j < s.size())
j++;
reverse(s,i,j-);
res += s.substr(i,j-i);
res += " ";
i = j;
}
}
res = res.substr(,res.size() - );
return res;
}
void reverse(string& s,int start,int end){
while(start < end){
char tmp = s[end];
s[end] = s[start];
s[start] = tmp;
end--;
start++;
}
return;
}
};