反转字符串里的单词
力扣题号151
题目描述：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| 给你一个字符串 s ，请你反转字符串中 单词 的顺序。
单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。
返回 单词 顺序颠倒且 单词 之间用单个空格连接的结果字符串。
注意：输入字符串 s中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格。
示例 1：
输入：s = "the sky is blue"
输出："blue is sky the"
示例 2：
输入：s = " hello world "
输出："world hello"
解释：反转后的字符串中不能存在前导空格和尾随空格。
示例 3：
输入：s = "a good example"
输出："example good a"
解释：如果两个单词间有多余的空格，反转后的字符串需要将单词间的空格减少到仅有一个。
|
首先我们确认 反转单词 不是单纯的反正反转单词的字符，而是反转单词的顺序，这个我们样例中可以看出。我们整理一下思路
这道题看起来复杂，实际上像是多个简单题的组合，再理清思路之后就变得简单，解法中主要用的是双指针
双指针
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
45
46
47
48
49
50
51
52
53
54
55
56
| class Solution {
public String reverseWords(String s) {
StringBuilder build = getBuild(s);
reverse(build, 0, build.length() - 1);
reverseWord(build);
return build.toString();
}
private StringBuilder getBuild(String s) {
int start = 0;
int end = s.length() - 1;
while (start <= end && s.charAt(start) == ' ') {
start++;
}
while (end >= start && s.charAt(end) == ' ') {
end--;
}
StringBuilder builder = new StringBuilder();
while (end >= start) {
if (s.charAt(start) != ' ' || builder.charAt(builder.length() - 1) != ' ') {
builder.append(s.charAt(start));
}
start++;
}
return builder;
}
private void reverse(StringBuilder chars, int start, int end) {
while (start < end) {
char tmp = chars.charAt(start);
chars.setCharAt(start, chars.charAt(end));
chars.setCharAt(end, tmp);
start++;
end--;
}
}
private void reverseWord(StringBuilder s) {
int start = 0;
int end = 0;
int length = s.length();
while (start < length) {
while (end < length && s.charAt(end) != ' ') {
end++;
}
reverse(s, start, end - 1);
start = end + 1;
end++;
}
}
}
|
