原文链接: https://leetcode-cn.com/problems/zuo-xuan-zhuan-zi-fu-chuan-lcof
中文题目
字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如，输入字符串"abcdefg"和数字2，该函数将返回左旋转两位得到的结果"cdefgab"。
示例 1：
输入: s = "abcdefg", k = 2 输出: "cdefgab"
示例 2：
输入: s = "lrloseumgh", k = 6 输出: "umghlrlose"
限制：
1 <= k < s.length <= 10000
通过代码
高赞题解
解题思路：
本题做法较多，本文主要介绍 “字符串切片” ， “列表遍历拼接” ， “字符串遍历拼接” 三种方法。
由于本题的多解法涉及到了 字符串为不可变对象 的相关概念，导致效率区别较大。因此，单列一节 三种方法的效率分析 ，望对各位有所帮助。
方法一：字符串切片
应用字符串切片函数，可方便实现左旋转字符串。
获取字符串 $s[n:]$ 切片和 $s[:n]$ 切片，使用 “$+$” 运算符拼接并返回即可。
复杂度分析：
- 时间复杂度 $O(N)$ ： 其中 $N$ 为字符串 $s$ 的长度，字符串切片函数为线性时间复杂度（参考资料）；
- 空间复杂度 $O(N)$ ： 两个字符串切片的总长度为 $N$ 。
{:width=450}
代码：
[]class Solution: def reverseLeftWords(self, s: str, n: int) -> str: return s[n:] + s[:n]
[]class Solution { public String reverseLeftWords(String s, int n) { return s.substring(n, s.length()) + s.substring(0, n); } }
方法二：列表遍历拼接
若面试规定不允许使用 切片函数 ，则使用此方法。
算法流程：
- 新建一个 list(Python)、StringBuilder(Java) ，记为 $res$ ；
- 先向 $res$ 添加 “第 $n + 1$ 位至末位的字符” ；
- 再向 $res$ 添加 “首位至第 $n$ 位的字符” ；
- 将 $res$ 转化为字符串并返回。
复杂度分析：
- 时间复杂度 $O(N)$ ： 线性遍历 $s$ 并添加，使用线性时间；
- 空间复杂度 $O(N)$ ： 新建的辅助 $res$ 使用 $O(N)$ 大小的额外空间。
{:width=550}
代码：
[]class Solution: def reverseLeftWords(self, s: str, n: int) -> str: res = [] for i in range(n, len(s)): res.append(s[i]) for i in range(n): res.append(s[i]) return ''.join(res)
[]class Solution { public String reverseLeftWords(String s, int n) { StringBuilder res = new StringBuilder(); for(int i = n; i < s.length(); i++) res.append(s.charAt(i)); for(int i = 0; i < n; i++) res.append(s.charAt(i)); return res.toString(); } }
利用求余运算，可以简化代码。
[]class Solution: def reverseLeftWords(self, s: str, n: int) -> str: res = [] for i in range(n, n + len(s)): res.append(s[i % len(s)]) return ''.join(res)
[]class Solution { public String reverseLeftWords(String s, int n) { StringBuilder res = new StringBuilder(); for(int i = n; i < n + s.length(); i++) res.append(s.charAt(i % s.length())); return res.toString(); } }
方法三：字符串遍历拼接
若规定 Python 不能使用
join()函数，或规定 Java 只能用 String ，则使用此方法。
此方法与 方法二 思路一致，区别是使用字符串代替列表。
复杂度分析：
- 时间复杂度 $O(N)$ ： 线性遍历 $s$ 并添加，使用线性时间；
- 空间复杂度 $O(N)$ ： 假设循环过程中内存会被及时回收，内存中至少同时存在长度为 $N$ 和 $N-1$ 的两个字符串（新建长度为 $N$ 的 $res$ 需要使用前一个长度 $N-1$ 的 $res$ ），因此至少使用 $O(N)$ 的额外空间。
{:width=550}
[]class Solution: def reverseLeftWords(self, s: str, n: int) -> str: res = "" for i in range(n, len(s)): res += s[i] for i in range(n): res += s[i] return res
[]class Solution { public String reverseLeftWords(String s, int n) { String res = ""; for(int i = n; i < s.length(); i++) res += s.charAt(i); for(int i = 0; i < n; i++) res += s.charAt(i); return res; } }
同理，利用求余运算，可以简化代码。
[]class Solution: def reverseLeftWords(self, s: str, n: int) -> str: res = "" for i in range(n, n + len(s)): res += s[i % len(s)] return res
[]class Solution { public String reverseLeftWords(String s, int n) { String res = ""; for(int i = n; i < n + s.length(); i++) res += s.charAt(i % s.length()); return res; } }
效率分析：
详细分析请参考 Efficient String Concatenation in Python 。
以上三种方法的空间使用如下图所示。
以 Python 为例开展三种方法的效率测试，结论同样适用于 Java 等其他语言。
{:width=550}
测试数据：
长度为 $10000000$ 的全为 '1' 的字符串。
s = "1" * 10000000方法一测试：
新建两切片字符串，并将两切片拼接为结果字符串，无冗余操作，效率最高。
[]# 运行时间: 0.01 秒 def func1(s): cut = len(s) // 3 return s[:cut] + s[cut:]
方法二测试：
列表(Python) 和 StringBuilder(Java) 都是可变对象，每轮遍历拼接字符时，只是向列表尾部添加一个新的字符元素。最终拼接转化为字符串时，系统 仅申请一次内存 。
[]# 运行时间: 1.86 秒 def func2(s): res = [] for i in range(len(s)): res.append(s[i]) # 仅需在列表尾部添加元素 return ''.join(res)
方法三测试：
在 Python 和 Java 中，字符串是 “不可变对象” 。因此，每轮遍历拼接字符时，都需要新建一个字符串；因此，系统 需申请 $N$ 次内存 ，数据量较大时效率低下。
[]# 运行时间: 6.31 秒 def func3(s): res = "" for i in range(len(s)): res += s[i] # 每次拼接都需要新建一个字符串 return res
统计信息
| 通过次数 | 提交次数 | AC比率 |
|---|---|---|
| 227715 | 265259 | 85.8% |
提交历史
| 提交时间 | 提交结果 | 执行时间 | 内存消耗 | 语言 |
|---|
