Reverse Words in a String
LeetCode #151
Description:
Given an input string, reverse the string word by word.
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.
Example:
Given s = " the sky is blue ",
return "blue is sky the".
Idea:
reverse each word, then reverse the whole sentence.
但是,处理各种heading, training和多余的spacing很难。
Code:
class Solution {
public:
void reverseWords(string &s) {
int i=0, j; // left and right of one word
int icurr=0; // current copy position
int n=s.size();
int count=0; // how many words has been copied
while(i!=n){
while(i!=n && s[i]==' '){ // Until non space is found
++i;
}
j=i;
while(j!=n && s[j]!=' '){ // Until space is found
j++;
}
if(i!=n){
reverseSingleWord(s, i, j-1); // reverse one word
count++;
}
if(count>1 && i!=n){ //如果不是第一个word或者i已经到头了
icurr++;
}
while(i!=j){ // Copy one word
s[icurr++] = s[i++];
}
if(icurr!=n){ // Avoid out of range
s[icurr]=' '; // Set one space between words
}
}
s.erase(icurr);
reverseSingleWord(s, 0, s.size()-1); // reverse the whole sentence
}
void reverseSingleWord(string &s, int i, int j){
while(i<j){
swap(s[i], s[j]);
i++;
j--;
}
}
};