代码随想录算法训练营第9天｜字符串Part02
记录题目：
- 反转字符串中的单词
- 右旋字符串
- 找出字符串中第一个匹配项的下标
对于数组，不方便使用模拟时，可以观察操作是否可以分解为多个反转实现。
给你一个字符串
s，请你反转字符串中 单词 的顺序。单词 是由非空格字符组成的字符串。
s中使用至少一个空格将字符串中的 单词 分隔开。返回 单词 顺序颠倒且 单词 之间用单个空格连接的结果字符串。
注意：输入字符串
s中可能会存在前导空格、尾随空格或者单词间的多个空格。
字符串的右旋转操作是把字符串尾部的若干个字符转移到字符串的前面。给定一个字符串 s 和一个正整数 k，将字符串中后 k 个字符移到前面，实现字符串的右旋转操作。
例如： 输入：”abcdefg” 和整数 2 输出：”fgabcde”
何时可以考虑“用多个反转实现”？
可以在遇到以下场景时主动问自己：
| 场景 | 是否可考虑用反转实现？ | 举例 |
|---|---|---|
| 顺序整体调整（旋转、调头） | YES | 右旋字符串、反转单词 |
| 局部搬移或重复移动 | YES | 将后半部分移到前面 |
| 不能开新数组 | YES | 原地操作要求，推荐 reverse 模式 |
| 每次操作都是“范围交换” | YES | 将一段一段翻转、调换 |
如何自发产生“用反转实现”的思路？
| 步骤 | 要做的事 |
|---|---|
| ① | 观察目标状态和初始状态结构 |
| ② | 问自己：能否通过“反转”一步步得到？ |
| ③ | 小规模模拟 + index 分析 |
| ④ | 总结归纳成模式，下次复用 |
给你两个字符串
haystack和needle，请你在haystack字符串中找出needle字符串的第一个匹配项的下标（下标从 0 开始）。如果needle不是haystack的一部分，则返回-1。
在实现 KMP 算法时，我使用的 next 数组定义为：next[i] 表示字符串从下标 0 到 i 这一闭区间 [0, i] 中，最长相等前后缀的长度。
在构造 next 数组的过程中，较难理解的一点是：在当前位置 i 的字符与当前前缀末位 j 不相等时，需要将 j 回退为 next[j - 1]。这一操作的本质是：我们试图构造以 arr[i] 结尾的子串 [0, i] 的最长相等前后缀。若当前 arr[i] !== arr[j]，说明此前构造的前缀（长度为 j）无法继续延伸，此时不应直接放弃，而是寻找次长的前缀尝试匹配。
这等价于将原问题转化为：寻找 j 所代表的前缀（即 [0, j - 1]）自身的最长相等前后缀，并尝试将 arr[i] 追加其后，看是否能形成新的匹配。
因此，令 j = next[j - 1]，继续尝试，直到 arr[i] === arr[j] 或 j 回退为 0。
这正是 KMP 算法在构造 next 数组时最精妙的地方：充分利用已知的匹配结构，避免重复计算，逐步回退尝试较短的匹配前缀。这一过程本质上是一种“匹配状态的继承”。
