字符串——剑指 Offer 58 - II. 左旋转字符串

1 题目描述

剑指 Offer 58 - II. 左旋转字符串

字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如，输入字符串"abcdefg"和数字2，该函数将返回左旋转两位得到的结果"cdefgab"。

2 题目示例

示例 1： 输入: s = “abcdefg”, k = 2 输出: “cdefgab”

示例 2： 输入: s = “lrloseumgh”, k = 6 输出: “umghlrlose”

3 题目提示

1 <= k < s.length <= 10000

4 思路

本题做法较多，本文主要介绍 “字符串切片” ， “列表遍历拼接” ， “字符串遍历拼接” 三种方法。 由于本题的多解法涉及到了 字符串为不可变对象 的相关概念，导致效率区别较大。因此，单列一节 三种方法的效率分析 ，望对各位有所帮助。

方法一:字符串切片 应用字符串切片函数，可方便实现左旋转字符串。 获取字符串s[n :]切片和s[:n]切片，使用"+"运算符拼接并返回即可。 复杂度分析: 时间复杂度o(N):其中N为字符串s的长度，字符串切片函数为线性时间复杂度; 空间复杂度o(N):两个字符串切片的总长度为N。

方法二:列表遍历拼接 若面试规定不允许使用切片函数，则使用此方法。 算法流程: 1.新建一个 list(Python)、StringBuilder(Java)，记为res ; 2.先向res添加“第n＋1位至末位的字符”; 3.再向res添加“首位至第n位的字符”;4.将res转化为字符串并返回。 复杂度分析: 时间复杂度o(N):线性遍历s并添加，使用线性时间;。 空间复杂度O(N)︰新建的辅助res使用O(N)大小的额外空间

方法三:字符串遍历拼接 若规定Python不能使用join(函数，或规定Java只能用String，则使用此方法。 此方法与方法二思路—致，区别是使用字符串代替列表。 复杂度分析: 时间复杂度o(N):线性遍历s并添加，使用线性时间; 空间复杂度O(N):假设循环过程中内存会被及时回收，内存中至少同时存在长度为N和N―1的两个字符串(新建长度为N的res需要使用前一个长度Ⅳ-1的res ) ,因此至少使用O(N)的额外空间。

5 我的答案

方法一:字符串切片

class Solution {
    public String reverseLeftWords(String s, int n) {
        return s.substring(n, s.length()) + s.substring(0, n);
    }
}

方法二:列表遍历拼接

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 {
    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;
    }
}