参考剑指 Offer 58 - I. 翻转单词顺序
非原地解法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| class Solution {
public:
string reverseWords(string s) {
string ret;
int n = s.size();
int begin = n - 1, end = n - 1;
while(begin >= -1)
{
if(begin == -1 || s[begin] == ' ')
{
if(begin != end)
{
ret += s.substr(begin + 1, end - begin);
ret += ' ';
}
end = --begin;
}
else
--begin;
}
ret.pop_back();
return ret;
}
};
|
原地解法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| class Solution {
public:
string reverseWords(string s) {
reverse(s.begin(), s.end());
int idx = 0, end = 0, start = 0;
int n = s.size();
while(start < n)
{
if(s[start] != ' ')
{
end = start;
while(end < n && s[end] != ' ') s[idx++] = s[end++];
reverse(s.begin() + idx - (end - start), s.begin() + idx);
s[idx++] = ' ';
start = end;
}
++start;
}
s.erase(s.begin() + idx - 1, s.end());
return s;
}
};
|