思想:操作分解
- 翻转整个链表
- 翻转每个单词
原地算法: 时间复杂度$O(N)$ 空间复杂度$O(1)$
下面代码 用来找以空格为分隔的子串(单词)
i
~ j - 1
是要找的子串,j
指向空格
for (int i = 0; i < s.size(); i ++) {
int j = i + 1;
while (j < s.size() && s[j] != ' ') j ++;
class Solution {
public:
string reverseWords(string s) {
// 1. 翻转整个链表
for (int i = 0, j = s.size() - 1; i < j; i ++, j --) swap(s[i], s[j]);
//上面可以用reverse(s.begin(), s.end())代替
// 2. 翻转每个单词
for (int i = 0; i < s.size(); i ++) {
int j = i + 1;
while (j < s.size() && s[j] != ' ') j ++;
reverse(s.begin() + i, s.begin() + j);
i = j;
}
return s;
}
};