151. 反转字符串中的单词

题目描述

给定一个字符串 s，你需要反转字符串中每个单词的顺序，但是单词内部的字符顺序不变。每个单词的定义是：由空格分隔的连续非空格字符。

示例 1:

输入: "the sky is blue"
输出: "blue is sky the"

示例 2:

输入: "hello world"
输出: "world hello"

示例 3:

输入: "a good example"
输出: "example good a"

题解

为了实现原地算法，我们需要在字符串上直接操作，而不是创建新的字符串或使用额外的数组。以下是解决此问题的步骤：

1. 反转整个字符串：首先，我们需要反转整个字符串，因为这样做可以简化后续步骤。
2. 反转每个单词：然后，我们反转每个单词，因为第一步操作后，单词的顺序已经颠倒了，但单词内部的字符顺序也被颠倒了。

下面是使用 Go 语言实现的代码：

package main

import (
	"fmt"
	"unicode/utf8"
)

func reverse(s string, left int, right int) {
	runeStr := []rune(s)
	for left < right {
		runeStr[left], runeStr[right] = runeStr[right], runeStr[left]
		left++
		right--
	}
}

func reverseWords(s string) string {
	// 将字符串转换为rune切片，以便处理多字节unicode字符
	runeStr := []rune(s)
	left, right := 0, 0

	// 步骤1：反转整个字符串
	for right < len(runeStr)-1 {
		if runeStr[right] == ' ' || runeStr[right+1] == ' ' {
			reverse(string(runeStr), left, right)
			left = right + 1
		}
		right++
	}
	// 反转最后的单词（如果存在）
	if left < right {
		reverse(string(runeStr), left, right)
	}

	// 步骤2：反转每个单词
	left = 0
	for right < len(runeStr) {
		if runeStr[right] == ' ' {
			reverse(string(runeStr), left, right-1)
			left = right + 1
		} else if right == len(runeStr)-1 {
			reverse(string(runeStr), left, right)
		}
		right++
	}

	return string(runeStr)
}

func main() {
	fmt.Println(reverseWords("the sky is blue"))  // 输出: "blue is sky the"
	fmt.Println(reverseWords("hello world"))     // 输出: "world hello"
	fmt.Println(reverseWords("a good example"))  // 输出: "example good a"
}

复杂度分析

• 时间复杂度：O(n)，其中 n 是字符串 s 的长度。每个字符被遍历了几次，但总体上是线性的。
• 空间复杂度：O(1)，我们只使用了少量的额外空间。

这个解法是原地的，因为它直接在输入字符串上进行操作，没有使用额外的存储空间来存储单词或其反转。这种方法是空间效率很高的，因为它只使用了几个变量来跟踪边界和索引。