题目概述(简单难度)
字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如,输入字符串"abcdefg"和数字2,该函数将返回左旋转两位得到的结果"cdefgab"。
示例 1:
输入: s = "abcdefg", k = 2 输出: "cdefgab"
示例 2:
输入: s = "lrloseumgh", k = 6 输出: "umghlrlose"
题目链接:
点我进入leetcode
思路与代码
思路1(字符串切片)
应用字符串切片函数,可方便实现左旋转字符串。
获取字符串 s[n:]s[n:] 切片和 s[:n]s[:n] 切片,使用 “++” 运算符拼接并返回即可。
复杂度分析:
时间复杂度 O(N): 其中 N为字符串 s的长度,
空间复杂度 O(N): 两个字符串切片的总长度为 N 。
代码示例1
class Solution { public String reverseLeftWords(String s, int n) { return s.substring(n, s.length()) + s.substring(0, n); } }
思路2(列表遍历拼接)
若面试规定不允许使用 切片函数 ,则使用此方法。
算法流程:
新建一个 list(Python)、StringBuilder(Java) ,记为 res
先向 res 添加 “第 n + 1位至末位的字符” ;
再向 res添加 “首位至第 n位的字符” ;
将 res 转化为字符串并返回。
复杂度分析:
时间复杂度 O(N): 线性遍历 s并添加,使用线性时间;
空间复杂度 O(N) : 新建的辅助 res 使用 O(N)大小的额外空间。
代码示例2
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(); } }
总结
考察对于字符串库函数的使用.