剑指offer 58-I:翻转单词顺序
先把首尾的空格去掉,再用一个string类型vector把每个单词截取出来,倒序拼接。时间复杂度O(N);
LeetCode链接: 翻转单词顺序
自己撸的
class Solution {
public:
string reverseWords(string s) {
if(s.size() == 0)
return s;
int i = 0, j = s.size() - 1;
while(s[i] == ' ')
i ++ ;
while(s[j] == ' ')
j -- ;
s = s.substr(i, j - i + 1);
int len = s.size();
vector<string> res;
string temp = "";
for(int k = 0; k < len; k ++ ){
if(s[k] != ' ')
temp.push_back(s[k]);
else if(s[k] == ' ' && s[k - 1] != ' '){
res.push_back(temp);
temp = "";
}
}
res.push_back(temp);
string ans = "";
len = res.size();
for(int k = len - 1; k >= 0; k -- ){
ans.append(res[k]);
if(k > 0)
ans.push_back(' ');
}
return ans;
}
};
严格按照双指针
class Solution {
public:
string reverseWords(string s) {
if(s.size() == 0)
return s;
int i = 0, j = s.size() - 1;
while(s[i] == ' ')
i ++ ;
while(s[j] == ' ')
j -- ;
s = s.substr(i, j - i + 1);
int len = s.size();
string res = "";
i = len - 1, j = i;
while(i >= 0){
while(i >= 0 && s[i] != ' ')
i -- ;
res.append(s.substr(i + 1, j - i));
if(i > 0)
res.push_back(' ');
while(i >= 0 && s[i] == ' ')
i -- ;
j = i;
}
return res;
}
};