151.反转字符串中的单词

一、问题描述

给定一个字符串，你需要反转字符串中每个单词的字符顺序，同时保留空格和单词的初始顺序。

示例：

输入："Let's take LeetCode contest"
输出："s'teL ekat edoCteeL tsetnoc"

二、方案一：原地反转

1、思路

原地反转的方法是先反转整个字符串，然后逐个反转每个单词。这种方法不需要额外的空间来存储单词。

2、代码实现

func reverseWords(s string) string {
	arr := []byte(s)
	reverse(arr, 0, len(arr)-1)
	start := 0
	for i := 0; i <= len(arr); i++ {
		if i == len(arr) || arr[i] == ' ' {
			reverse(arr, start, i-1)
			start = i + 1
		}
	}

	// 删除首尾多余的空格
	start = 0
	end := len(arr) - 1
	for start <= end && arr[start] == ' ' {
		start++
	}
	for end >= start && arr[end] == ' ' {
		end--
	}

	// 删除中间的空格
	j := start
	for i := start; i <= end; i++ {
		if i > 0 && arr[i] == arr[i-1] && arr[i] == ' ' {
			continue
		}
		arr[j] = arr[i]
		j++
	}

	return string(arr[start:j])
}

func reverse(arr []byte, left int, right int) {
	for left < right {
		arr[left], arr[right] = arr[right], arr[left]
		left++
		right--
	}
}

3、复杂度分析

• 时间复杂度：O(n)，其中 n 是字符串的长度。我们需要遍历整个字符串两次。
• 空间复杂度：O(1)，我们只使用了常数级别的额外空间。