Reverse Words in a String
Given an input string, reverse the string word by word.
For example,
Given s = "
return "
Given s = "
the sky is blue",return "
blue is sky the".
------------------------------------------ thinking -------------------------------------------------------------------
I only considered the simplest situation. There are lots of edge cases I missed!!!
1. trim the string at the very beginning!!! there might be many spaces at the beginning and ending of the string, when reversing them, those spaces are excluded
2. trim the spaces between each words!!! we should shrink the spaces into one before doing reversing
3. when the loop reached the end of the string, the last word is not reversed!!!!
---------------------------------------------- codes --------------------------------------------------------------
class Solution {
public:
void reverseWords(string &s) {
//bug here
int done = trim_str(s);
if (done == 1) {
return;
}
string m;
for(int i=0;i<=s.size()-1;++i){
if(s[i]==' '&&s[i+1]==' ') continue;
else m.push_back(s[i]);
}
s = m;
int len = s.size();
int start = 0;
int state = 1;//0 -> letter 1 -> space
for (int i = 0; i < len; i++){
if (s[i] == ' ') {
if (state == 0) {
inplace_reverse(s, start, i - 1);
state = 1;
}
} else {
if (state == 1) {
start = i;
state = 0;
}
}
}
//bug here
inplace_reverse(s, start, len - 1);
inplace_reverse(s, 0, len - 1);
}
int trim_str(string &s) {
int start = 0;
int len = s.size();
while ((s[start] == ' ') && (start != len)) {
start++;
}
if (start == len) {
s.clear();
return 1;
}
if (start > 0) {
s.erase(0, start);
}
int end = s.size() - 1;
while ((s[end] == ' ') && (end >= 0)) {
end--;
}
if (end < s.size() - 1) {
s.erase(end + 1, s.size() - end - 1);
}
if (s.size() == 1) {
return 1;
}
start = 0;
while ((s[start] != ' ') && (start < s.size())) {
start ++;
}
if (start != s.size()) {
return 0;
} else {
return 1;
}
}
void inplace_reverse(string &s, int start, int end) {
//int len = s.size()
//assert(start >=0 && start < len && end >= 0 && end < len && start <= end);
if (start > end) {
return;
}
//bug here
while (start < end) {
char tmp = s[start];
s[start] = s[end];
s[end] = tmp;
start++;
end--;
}
return;
}
};
No comments:
Post a Comment