题目描述：
给出一个字符串 $s$ ，反正字符串中单词的顺序，去除首尾空格，以及单词间的多个空格，单词之间只用一个空格隔开。
数据范围：
$1\le n \le 10^4$
题解：
使用 $O(1)$ 的空间，需要原地翻转。分成三步：
其中去除多余空格过程和翻转单词过程可以使用双指针一起维护。使用 start维护后续需要接单词的位置。 $[l,r]$ 为需要翻转的单词，翻转之后复制到 start之后。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
| auto optimize_cpp_stdio = []()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
return 0;
}();
class Solution
{
public:
void reverseString(string &s, int l, int r)
{
for (int i = l, j = r; i < j; ++i, --j)
{
swap(s[i], s[j]);
}
}
string reverseWords(string &s)
{
int n = s.size();
reverseString(s, 0, n - 1);
int l = 0, r = 0, start = 0, end = n;
while (l < n)
{
if (start != 0)
s[start++] = ' ';
while (l < n && s[l] == ' ')
l++;
if (l == n)
{
start--;
break;
}
r = l;
while (r < n && s[r] != ' ')
r++;
reverseString(s, l, r - 1);
while (l < r)
s[start++] = s[l++];
}
s.erase(s.begin() + start, s.end());
return s;
}
};
|