反转字符串中的单词

怎样从“给定字符串 s，反转单词顺序，删除首尾空格、压缩连续空格。例：" hello world " → "world hello"”推导出 字符串 · 双指针 · 空格压缩 · 整体反转 + 局部反转，并证明每次状态变化都不会漏掉答案？

中心结论：工程版 strings.Fields + 双指针反转数组；follow-up 原地：压缩空格 → 整体反转 → 逐词反转。

给定一个字符串，逐个翻转字符串中的每个单词。

无空格字符构成一个单词。 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。

请选用 C 语言的用户尝试使用 O(1) 额外空间复杂度的原地解法。

在本站主例中，给定字符串 s，反转单词顺序，删除首尾空格、压缩连续空格。例：" hello world " → "world hello"

算法最终需要得到或观察："world hello"（多空格样例）或 "blue is sky the"（干净样例）。

每次失配都换起点并从 needle[0] 开始，会丢掉已经确认的前缀；LPS 保存可复用的最长相等真前后缀。

暴力方案的价值是确认题意并提供正确性基线。它通常会覆盖所有候选， 但没有保存已经确认的信息，因此同一状态会被重新计算。

1. 1建模把输入翻译成“模式串自救地图”，明确答案需要观察什么。
2. 2状态只维护 clean 阶段 fast/slow/needSpace；reverse 阶段 left/right；scan 阶段 wordStart/wordEnd；output 当前字符串。
3. 3转移每一步按照 工程版 strings.Fields + 双指针反转数组；follow-up 原地：压缩空格 → 整体反转 → 逐词反转。
4. 4收尾读取 "world hello"（多空格样例）或 "blue is sky the"（干净样例）。，并复核边界与复杂度。

失配不是清零，而是把模式串移动到下一个仍可能成功的位置。

这道题不是为了记住一个组件名称，而是为了让状态具有可解释的语义：clean 阶段 fast/slow/needSpace；reverse 阶段 left/right；scan 阶段 wordStart/wordEnd；output 当前字符串。

给出一个中间有空格分隔的字符串，要求把这个字符串按照单词的维度前后翻转。 依照题意，先把字符串按照空格分隔成每个小单词，然后把单词前后翻转，最后再把每个单词中间添加空格。

工程版 strings.Fields + 双指针反转数组；follow-up 原地：压缩空格 → 整体反转 → 逐词反转。

执行过程中持续维护：clean 阶段 fast/slow/needSpace；reverse 阶段 left/right；scan 阶段 wordStart/wordEnd；output 当前字符串。

正确性依赖以下不变量：压缩空格后无首尾空格，单词间仅一个空格。；整体反转改变词序；逐词反转恢复词内顺序。；两次反转组合 = 词序反转、词内不变。

面试时可以压缩为：工程：strings.Fields + 双指针反转 + Join，O(n) 时间 O(n) 空间。follow-up：[]byte 原地压缩空格、整体反转、逐词反转，O(n) 时间 O(1) 额外空间。

落到当前题，执行机制可以压缩为：工程版 strings.Fields + 双指针反转数组；follow-up 原地：压缩空格 → 整体反转 → 逐词反转。每一次更新都必须保持核心不变量，而不是只让样例碰巧得到正确答案。

1. 1题目与输入给定字符串 s，反转单词顺序，删除首尾空格、压缩连续空格。例：" hello world " → "world hello" 因为：工程版 strings.Fields + 双指针反转数组；follow-up 原地：压缩空格 → 整体反转 → 逐词反转。
2. 2分割单词后双指针交换先 split 再去多余空格。 因为：反转单词顺序。
3. 3交换 words[0] 与 words[1]双指针向内交换。 因为：O(n) 原地反转数组。
4. 4结果 'world hello'join 单词。 因为：也可以先 reverse 整个串再 reverse 每个单词。
5. 5分割单词后双指针交换先 split 再去多余空格。 因为：反转单词顺序。
6. 6预测下一步先不要看下一帧——根据当前不变量,预测算法接下来会怎么动。 因为：主动预测会暴露你对不变量的真实理解,比被动看动画有效得多。
7. 7收尾与复杂度"world hello"（多空格样例）或 "blue is sky the"（干净样例）。 因为：时间 O(n) · 空间 O(n) 工程版 · O(1) follow-up 额外空间。工程版 strings.Fields + 双指针反转数组；follow-up 原地：压缩空格 → 整体反转 → 逐词反转。

代码窗口不会按容易漂移的固定数字行号硬绑动画，而是根据当前语义阶段， 在完整 Go 实现中定位选择、计算、写回或返回分支。当前变量与高亮行一起变化。

import "strings"

func reverseWords(s string) string {
	ss := strings.Fields(s)
	reverse(&ss, 0, len(ss)-1)
	return strings.Join(ss, " ")
}

func reverse(m *[]string, i int, j int) {
	for i <= j {
		(*m)[i], (*m)[j] = (*m)[j], (*m)[i]
		i++
		j--
	}
}

func main() {
    // 1. 主例
    //    输入：mode="reverse-words", text="  hello   world  "
    //    期望："world hello"（多空格样例）或 "blue is sky the"（干净样例）。
    //
    // 2. 失败 / 未命中
    //    检查：只 reverse 整串忘记逐词反转。
    //
    // 3. 边界
    //    空输入、单元素、最小合法规模，以及答案恰好落在边界的情况。
    //
    // 4. 迁移
    //    LC125 回文；LC14 前缀
}

Go 参考实现基于 halfrost/LeetCode-Go 的 MIT 许可代码整理，并按本站教学结构补充解释与动画映射。

1. 1题意给定字符串 s，反转单词顺序，删除首尾空格、压缩连续空格。例：" hello world " → "world hello"
2. 2重复每次失配都换起点并从 needle[0] 开始，会丢掉已经确认的前缀；LPS 保存可复用的最长相等真前后缀。
3. 3优化工程版 strings.Fields + 双指针反转数组；follow-up 原地：压缩空格 → 整体反转 → 逐词反转。
4. 4证明压缩空格后无首尾空格，单词间仅一个空格。；整体反转改变词序；逐词反转恢复词内顺序。；两次反转组合 = 词序反转、词内不变。
5. 5复杂度时间 O(n)，空间 O(n) 工程版 · O(1) follow-up 额外空间