左旋转字符串

题目描述

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

示例 1：

1 2	输入: s = "abcdefg", k = 2 输出: "cdefgab"

示例 2：

1 2	输入: s = "lrloseumgh", k = 6 输出: "umghlrlose"

限制：
1 <= k < s.length <= 10000

题目链接

Leetcode

题目解答

解法一

比较直观的处理方式就是通过截取子串，然后重新拼接组合成目标字符串。

时间复杂度:$O(n)$ 空间复杂度:$O(n)$

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

执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
内存消耗：38.1 MB, 在所有 Java 提交中击败了88.91%的用户

解法二

借助一个与字符串长度相等的字符数组，从位置n处切分字符串，先把字符串后半段字符依次存入字符数组，再把字符串前半段字符依次存入字符数组，使用额外空间直接赋值的方式，避免了对原字符串对应字符数组元素的大量迁移，从而降低时间损耗。解法二与解法一处理方式从原理上来说是一致的，解法一使用的是字符串内置函数处理，底层使用了System.arraycopy，性能上比我们自己对字符数组赋值表现更好。

时间复杂度:$O(n)$ 空间复杂度:$O(n)$

class Solution {
    public String reverseLeftWords(String s, int n) {
        int index = 0;
        char[] chs = new char[s.length()];
        for (int i = n; i < s.length(); i++) {
            chs[index++] = s.charAt(i);
        }
        for (int i = 0; i < n; i++) {
            chs[index++] = s.charAt(i);
        }
        return new String(chs);
    }
}

执行结果执行用时：3 ms, 在所有 Java 提交中击败了35.46%的用户
内存消耗：37.9 MB, 在所有 Java 提交中击败了95.97%的用户