题目描述
给定一个字符串，逐个翻转字符串中的每个单词。
说明：
无空格字符构成一个单词。
输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。
请选用 C 语言的用户尝试使用 O(1) 额外空间复杂度的原地解法。
题解
先放一个空间复杂度为O(n)的：
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
| string reverseWords(string s) {
string word = "";
int i = 0, j = 0;
stack<string> stk;
while (s[i] == ' ')
i++;
j = i;
while (i < s.length())
{
while (j<s.length()&&s[j] != ' ')j++;
if (j == s.length())
{
if(j>i)
stk.push(s.substr(i, j - i));
break;
}
stk.push(s.substr(i, j - i));
while (s[j] == ' ')
j++;
i = j;
}
string res = " ";
while (!stk.empty())
{
word = stk.top();
stk.pop();
res =res+ word+" ";
}
if (res.length() == 1)return "";
return res.substr(1, res.length() - 2);
}
|
不过效率太低了。睡一觉再改吧。
先将字符串整个反转一下，然后再反转单个单词就行了。这其中可以去掉空格。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| string reverseWords(string s)
{
reverse(s.begin(), s.end());
int n = s.size();
int idx = 0;
for (int i = 0; i < n; i++)
{
if (s[i] != ' ')
{
if (idx != 0)
s[idx++] = ' ';
int j = i;
while (j < n&&s[j] != ' ')
{
s[idx++] = s[j++];
}
reverse(s.begin() + idx - (j - i), s.begin() + idx);
i = j;
}
}
s.erase(s.begin() + idx, s.end());
return s;
}
|