LeetCode 剑指 Offer 58 - II. 左旋转字符串
目录
题目描述
题意分析
输入一个字符串 s 和一个整数 n，要求把 s 前面的 n 个字符整体搬到字符串的尾部，返回搬运之后的新字符串。题面把这个动作叫做「左旋转」，但本质上只是一次位置重排，字符本身既不增加也不减少，出现次数也完全不变。
约束里透露的信号很直接：
1 <= n < s.length，也就是说旋转量严格小于长度，既不会出现「不旋转」的退化输入，也不会出现绕圈超过一整轮的情况。字符集是普通小写字母，没有多字节字符，因此可以放心按下标定位，不必担心索引落在半个字符中间。数据规模很小，$O(n)$ 的做法绰绰有余，题目真正想考的是你能不能一眼看穿「旋转 = 前后两段互换位置」，而不是老老实实地搬 n 次。边界方面唯一需要留意的是：如果题目放宽约束允许 n 大于等于长度，就必须先把 n 对长度取模，否则按下标截取会直接越界；空串则要在取模之前挡掉，避免除零。
解法：字符串切分
核心思路
最朴素的模拟是执行 n 轮操作，每一轮把首字符取下来接到末尾。这样做完全正确，但每一轮都要重排整个字符串，总代价是 $O(n \times len)$，而且中途产生了大量只存在一瞬间的中间串。瓶颈在于它把「一次整体重排」拆成了 n 次局部重排，重复搬运了同一批字符。
观察一下最终结果长什么样：设长度为
len，旋转量为n，那么答案的第 0 个字符是原串的第n个字符，第 1 个是原串第n + 1个……一直到原串末尾；紧接着才轮到原串的第 0 到第n - 1个字符。换句话说，原串被下标n切成了前缀s[0, n)和后缀s[n, len)两段，答案就是这两段调换顺序后的拼接，段内部的相对顺序丝毫未变。于是不变量可以写成：答案等于
s[n, len) + s[0, n)，且对任意i，答案的第i位就是原串的第(i + n) mod len位。这个恒等式一次性描述了全部结果，不需要任何中间状态，因此只要按这个公式构造一次字符串即可，中间过程可以完全跳过。
解题步骤
第一步，取出字符串长度
len。之所以要先拿到长度，是因为后面的切分点和取模都依赖它，把它缓存下来也避免在表达式里反复调用长度方法。第二步，执行
n %= len（Go 版本写作k := n % len(s)）。虽然题目保证n < len，取模在这种输入下等价于不做任何事，但它让函数对「转一整圈回到原点」这类扩展输入也成立，是一个零成本的健壮性保险。Go 版本额外在取模前判断了空串并直接返回，因为对长度为 0 的串取模会触发除零。第三步，截取后缀
s.substring(n)，它对应旋转后排在最前面的那一段。选择从n开始而不是n - 1或n + 1，是因为下标为n的字符恰好是「没有被搬走的第一个字符」，前 n 个字符的下标范围是 0 到n - 1。第四步，截取前缀
s.substring(0, n)，它对应被搬到末尾的那一段。Java 的substring是左闭右开的，所以右端写n才能恰好取到n个字符。第五步，把后缀和前缀按这个顺序拼接并返回。顺序不能反，反过来就变成了右旋转。整个过程只构造了一次新串，没有任何循环。
以
s = "abcdefg"、n = 2走一遍：len = 7，取模后n仍为 2；后缀s.substring(2)从下标 2 取到末尾，得到"cdefg"；前缀s.substring(0, 2)取下标 0 和 1 两个字符，得到"ab"；拼接得到"cdefgab"，正好是把a、b两个字符搬到尾部的结果。再验证一下恒等式：答案第 0 位是c，而(0 + 2) mod 7 = 2，原串下标 2 正是c；答案第 5 位是a，(5 + 2) mod 7 = 0，原串下标 0 正是a，完全吻合。
代码实现
class Solution {
// 注意 n 可能大于长度，需要取模。
public String reverseLeftWords(String s, int n) {
int len = s.length();
n %= len;
return s.substring(n) + s.substring(0, n);
}
}
func reverseLeftWords(s string, n int) string {
// 注意 n 可能大于长度，需要取模。
if len(s) == 0 {
return s
}
k := n % len(s)
return s[k:] + s[:k]
}
复杂度分析
- 时间复杂度：$O(n)$，其中 n 为字符串长度。两次截取各自复制一段字符，拼接再把两段写入结果，每个字符总共被复制常数次。
- 空间复杂度：$O(n)$。Java 与 Go 的字符串都不可变，无法原地改写，必须新建一个等长的结果串，这部分空间是题目本身要求的输出，除此之外没有额外开销。
关键点总结
- 把「重复执行 k 次的操作」先展开看终态：很多旋转、移位、循环右移类题目一旦写出「答案第 i 位来自原串第
(i + n) mod len位」这样的闭式，模拟循环就自动消失了。- 切分点的语义要说清楚：下标
n是「留在原地的第一个字符」，前缀长度恰好是n，把这句话背下来可以避免在左闭右开区间上反复试错。- 取模是旋转类问题的标配前置动作：即使当前约束保证不越界，加上它的成本为零，却能让代码对更一般的输入直接成立。
- 明确不可变字符串的空间下界：面试官如果追问「能不能 $O(1)$ 空间」，正确回答是 Java/Go 的字符串不可变所以做不到，但若输入换成字符数组，就可以用「先整体反转、再分别反转两段」的三次反转法原地完成。
- 面试视角：先说 n 次模拟的 $O(n \times len)$ 及其瓶颈，再给出切片拼接的一行解，最后主动补充字符数组场景下的三次反转法和取模处理，这条从模拟到公式再到原地优化的链路，比直接甩出一行
substring更能体现思考过程。
易错点总结
- 拼接顺序写反成
s.substring(0, n) + s.substring(n)：s = "abcdefg"、n = 2会原样返回"abcdefg"，因为这等价于把串在下标 2 处切开又按原顺序接回去。- 误把后缀起点写成
s.substring(n - 1)：同样的用例会返回"bcdefgab"，字符b被复制了两份，结果长度变成 8。- 把前缀右端写成
n - 1：s.substring(0, n - 1)在n = 2时只取到"a"，结果"cdefga"丢了一个字符，长度短了 1。- 空串时不做保护直接取模：
s = ""、n = 3在 Java 里n %= 0抛出算术异常，Go 里同样触发整数除零 panic。- 忘记取模而 n 大于长度：
s = "abc"、n = 5会调用s.substring(5)，直接抛出越界异常，而正确答案应是取模后等价于n = 2的"cab"。- 用循环逐字符搬运且每轮都做字符串拼接：
s长度一万、n为五千时会产生五千个中间串，时间退化到平方级并触发大量垃圾回收。- 把「左旋转」理解成整体反转：对
s = "abcdefg"返回"gfedcba"，字符相对顺序被破坏，而本题要求两段内部顺序保持不变。- 想当然地对索引取模却忘了处理负数：如果自行推广到「左旋转 n 位，n 可能为负」的版本，
n = -1时 Java 的%会得到负余数，substring立刻越界，需要写成((n % len) + len) % len。- 在 Go 里对含中文等多字节字符的串按字节切分：
s = "中国人"、n = 1会从字节下标 1 处切开，切出半个 UTF-8 码点，输出乱码，此时应先转成[]rune再切。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 48. 旋转图像 | 中等 | 二维矩阵的原地旋转，靠转置加行反转实现 |
| 61. 旋转链表 | 中等 | 链表右旋，需先成环再按取模后的位置断开 |
| 151. 反转字符串中的单词 | 中等 | 以单词为单位反转，还要处理多余空格 |
| 186. 反转字符串中的单词 II | 中等 | 字符数组上原地完成，正是三次反转法的标准考场 |
| 189. 轮转数组 | 中等 | 数组可变，可用三次反转做到 $O(1)$ 额外空间 |
| 344. 反转字符串 | 简单 | 三次反转法的最小组成单元，纯双指针对撞 |
| 541. 反转字符串 II | 简单 | 按固定步长分段反转，重点在末尾不足一段的处理 |
| 557. 反转字符串中的单词 III | 简单 | 只反转每个单词内部，单词之间的顺序保持不变 |
| 796. 旋转字符串 | 简单 | 判断能否由旋转得到，用 s + s 包含判断一步解决 |
| 848. 字母移位 | 中等 | 移动的是字符取值而非位置，靠后缀和累计位移量 |
| 917. 仅仅反转字母 | 简单 | 反转时要跳过非字母字符并保持它们的原位置 |