151-颠倒字符串中的单词.md

151. 颠倒字符串中的单词

leecode原题

题目

给你一个字符串 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) 额外空间复杂度的 原地 解法。

解题思路

思路

我们挑战一下使用O(1)空间复杂度的解法，即只在原字符数组上进行操作.

整体思路:

1. 移除多余空格(包括字符串开头、结尾以及字符之间多余1个空格的其他空格)
2. 将整个字符串反转
3. 将每个单词反转(字符串按空格切分为多个单词，单词内部再次反转)

比如说，原字符串为：" the sky is blue "

1. 移除多余空格 : "the sky is blue"
2. 字符串反转："eulb si yks eht"
3. 单词反转："blue is sky the"

难点:
如何原地进行空格移除，这里就需要借用到快慢指针的用法了。

• 定义快慢指针
• 快指针向前移动，碰到非空字符时，将快指针的值赋给慢指针(额外要注意判断是不是字符串开头以及是单词的第一个字母，是的话，需要做一个空格的补充)

实现

源码

func reverseWords(s string) string {
	b := []byte(s)
	bLen := len(b)

	/*---------------------1. 移除空格(开头、结尾以及单词之间多余一个的空格)----------------------*/
	slowIndex := 0 // 定义慢指针
	fastIndex := 0 // 定义快指针
	for ; fastIndex < bLen; fastIndex++ {
		// 遇到非空字符, 要考虑单词前面还需要填充一个空格
		if b[fastIndex] != ' ' {
			// 非字符串开头遇到空格(判断fastIndex前一位是不是空格, 是空格即是单词的第一个开头字符)
			if slowIndex != 0 && b[fastIndex-1] == ' ' {
				b[slowIndex] = ' '
				slowIndex++
			}
			b[slowIndex] = b[fastIndex]
			slowIndex++
		}
	}
	// 重新调整数组大小
	b = b[:slowIndex]

	/*---------------------2. 进行整个字符串的反转----------------------*/
	reverseString(b, 0, len(b)-1)
	/*---------------------3. 进行单词内部之间的反转----------------------*/
	start := 0
	end := 0
	for ; end < len(b); end++ {
		// 碰到空字符, 代表从start到end之间是一个单词
		if b[end] == ' ' {
			reverseString(b, start, end-1)
			start = end + 1
		}
		// 代表是最后一个字符
		if end == len(b)-1 {
			reverseString(b, start, end)
		}
	}
	return string(b)
}

func reverseString(b []byte, start, end int) {
	for start < end {
		b[start], b[end] = b[end], b[start]
		start++
		end--
	}
}