倒序遍历
题目要求反转单词顺序，同时去掉多余空格，因此可以直接从后往前遍历字符串，每次提取一个完整单词加入答案。
做法是从字符串末尾开始，先跳过空格，再找到当前单词的左右边界，将该单词加入结果。之后继续向前重复这一过程。由于是按从后往前提取，所以最终拼接出的字符串天然就是单词逆序，同时只在单词之间手动加一个空格即可避免多余空格。
时间复杂度 $O(n)$
空间复杂度 $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
32
33
34
| class Solution {
public String reverseWords(String s) {
StringBuilder sb = new StringBuilder();
int end = s.length() - 1;
for (;;) {
int[] cur = getWord(s, end);
end = cur[0] - 1;
if (cur[0] == -1) {
break;
}
sb.append(s, cur[0], cur[1]);
sb.append(' ');
}
if (sb.length() > 0) {
sb.setLength(sb.length() - 1);
}
return sb.toString();
}
private int[] getWord(String s, int i) {
int[] ans = new int[]{-1, -1};
while (i >= 0 && s.charAt(i) == ' ') {
i--;
}
if (i >= 0) {
ans[1] = i + 1;
while (i >= 0 && s.charAt(i) != ' ') {
i--;
}
ans[0] = i + 1;
}
return ans;
}
}
|
双指针
也可以先去掉首尾空格，然后用双指针在字符串中从右往左扫描。
设 $r$ 和 $l$ 都指向当前待处理单词的末尾，先让 $l$ 左移找到这个单词的起点，再把这一段加入答案。随后继续跳过前面的空格，并更新下一轮单词的右边界。这样同样能够按逆序提取所有单词。
这种写法更紧凑，本质上仍然是从后往前逐个找单词。
时间复杂度 $O(n)$
空间复杂度 $O(n)$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution {
public String reverseWords(String s) {
s = s.trim();
int r = s.length() - 1, l = r;
StringBuilder ans = new StringBuilder();
while (l >= 0) {
while (l >= 0 && s.charAt(l) != ' ') {
l--;
}
ans.append(s, l + 1, r + 1).append(' ');
while (l >= 0 && s.charAt(l) == ' ') {
l--;
}
r = l;
}
return ans.toString().trim();
}
}
|