151. 翻转字符串里的单词

mid

给你一个字符串 s ，逐个翻转字符串中的所有单词。

单词是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的单词分隔开。

请你返回一个翻转 s 中单词顺序并用单个空格相连的字符串。

示例 1：

1
2
输入：s = "the sky is blue"
输出："blue is sky the"

示例 2：

1
2
3
输入：s = "  hello world  "
输出："world hello"
解释：颠倒后的字符串中不能存在前导空格和尾随空格。

双指针

目标是：原地反转，空间复杂度 $O(1)$

去空格：快慢指针
整体反转：头尾指针
部分反转：头尾指针

要注意去空格的边界条件，因为每一次循环，slow 最后要 +1 留一个空格，所以字符串末尾有空格和没空格是有区别的。

 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
func reverse(b []byte) {
	l, r := 0, len(b)-1
	for l <= r {
		b[l], b[r] = b[r], b[l]
		l++
		r--
	}
}

func reverseWords(s string) string {
	b := []byte(s)
	// 移除多余空格
	slow, fast := 0, 0

	for fast < len(b) {
		// 寻找一个单词的开头
		for fast < len(b) && b[fast] == ' ' {
			fast++
		}
		for fast < len(b) && b[fast] != ' ' {
			b[slow], b[fast] = b[fast], b[slow]
			slow++
			fast++
		}
		slow++
	}
	if b[slow-2] == ' ' {
		// 字符末尾有空格
		b = b[:slow-2]
	} else {
		// 字符末尾无空格
		b = b[:slow-1]
	}

	reverse(b)
	slow, fast = 0, 0
	for fast < len(b) {
		for slow < len(b) && b[slow] == ' ' {
			slow++
		}
		fast = slow
		for fast < len(b) && b[fast] != ' ' {
			fast++
		}
		reverse(b[slow:fast])

		slow = fast
	}
	return string(b)
}