這道題有In place and non In place兩種做法。in place的做法是，先把所有單詞逐一翻轉(zhuǎn)山林，再最后翻轉(zhuǎn)整個(gè)句子(151由于空格蔑担，需要extra check)
In place:
class Solution {
public:
void reverseWords(string &s) {
if(s.empty()) return;
int left = 0;
for(int i=0; i<=s.length(); i++){
if(i == s.length() || s[i] == ' '){
myReverse(s, left, i-1);
left = i+1;
}
}
reverse(s.begin(), s.end());
}
void myReverse(string &s, int start, int end){
while(start < end){
swap(s[start], s[end]);
start++; end--;
}
}
};
In place with character array:
class Solution {
public:
void reverse_util(vector<char>& str, int left, int right) {
reverse(str.begin() + left, str.begin() + right);
}
void reverseWords(vector<char>& str) {
if(str.empty()) {
return;
}
int left = 0;
for(int i=0; i<=str.size(); i++) {
if(i == str.size() || str[i] == ' '){
reverse_util(str, left, i);
left = i+1;
}
}
reverse(str.begin(), str.end());
}
};
With extra memory:
class Solution {
public:
void reverseWords(string &s) {
if(s.empty()) return;
int cur_len = 0;
string ret = "";
for(int i=s.length()-1; i>=0; i--){
if(s[i] == ' '){
if(cur_len == 0) continue;
else{
string word = s.substr(i+1, cur_len);
ret += word;
ret += ' ';
cur_len = 0;
}
}else{
cur_len++;
}
}
if(cur_len > 0) ret += s.substr(0, cur_len);
s = ret;
while(s.length() > 1 && s[0] == ' ') s.erase(0, 1);
while(s.back() == ' ') s.pop_back();
}
};
