题目

给你一个字符串 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 <= s.length <= 104
s 包含英文大小写字母、数字和空格 ' '
s 中至少存在一个 单词

进阶：如果字符串在你使用的编程语言中是一种可变数据类型，请尝试使用 O(1) 额外空间复杂度的 原地 解法。

思路

还没看到进阶时候，第一反应就是起一个新字符串，先处理掉多余的空格，然后整体反转后，再反转一个个单词即可。但是看到进阶之后，自然是要接受挑战了。

Go的字符串不能直接用下标定位赋值，所以需要先转成byte数组。其实Go中这个强转过程会发生拷贝（可以打印地址验证下），也就是空间复杂度其实并不符合。不过想要实现无拷贝转换需要使用unsafe包，感觉这里就不纠结这个问题了，主要是看下思路~

去除多余空格

开始我尝试在一次遍历中兼顾反转和过滤空格，不过发现心智负担太高，暂时搞不定，所以拆解成两个步骤，先去掉多余的空格。

多余就是指头尾空格，和单词之间多于一个的空格

头尾不用多说，主要问题就是在于中间空格的处理了。这里很常用的办法就是双指针法了。

快指针先跨过头部空格

后续只往慢指针处赋予非空格和第一个空格，直到结束

直到结束遍历，尾部至多留有一个空格，再行判断去除即可

反转

反转就简单多了，直接首尾两个指针对向移动，交换元素直到相遇

思路差不多就这样了，细节在代码注释了，上代码~

代码

个人递归解法

func reverseWords(s string) string {
	sBytes := []byte(s)

	// 使用双指针去除空格
	slow, fast := 0, 0
	// 头部空格部分等待被实际内容替换即可，无需现在处理
	for fast < len(sBytes) && sBytes[fast] == ' ' {
		fast++
	}
	for fast < len(sBytes) {
		// 非空格或者第一个空格，需要填充到头部
		if sBytes[fast] != ' ' ||
			(sBytes[fast] == ' ' && sBytes[fast-1] != ' ') {
			sBytes[slow] = sBytes[fast]
			fast++
			slow++
		} else if sBytes[fast] == ' ' && sBytes[fast-1] == ' ' {
			// 中间多余的空格，需要跳过
			fast++
		}
	}
	// 看最后一个放进去的是不是空格，有则说明尾部有空格，截掉它
	if slow > 0 && sBytes[slow-1] == ' ' {
		sBytes = sBytes[:slow-1]
	} else {
		sBytes = sBytes[:slow]
	}

	// 整体反转字符串
	reverse(&sBytes, 0, len(sBytes)-1)

	// 逐步反转每个单词
	start, end := -1, -1
	// 把超出数组的下标放进来，兼容最后一个单词的情况
	for i := 0; i <= len(sBytes); i++ {
		// 最后一个单词的情况，外加遇到空格时，就是扫描到了一个单词，需要执行单词反转
		if i == len(sBytes) || sBytes[i] == ' ' {
			end = i - 1
			reverse(&sBytes, start, end)
			start = -1
			end = 0
		} else if sBytes[i] != ' ' && start == -1 {
			// start未赋值时，第一次非空格就是新单词的起点
			start = i
		}
	}
	return string(sBytes)
}

func reverse(s *[]byte, start, end int) {
	for start < end {
		(*s)[start], (*s)[end] = (*s)[end], (*s)[start]
		start++
		end--
	}
}

半亩房顶

LeetCode-151. 反转字符串中的单词

题目

思路

去除多余空格

反转

代码

个人递归解法

LeetCode-155. 最小栈