左旋转字符串

题目描述

汇编语言中有一种移位指令叫做循环左移（ROL），现在有个简单的任务，就是用字符串模拟这个指令的运算结果。对于一个给定的字符序列S，请你把其循环左移K位后的序列输出。例如，字符序列S=”abcXYZdef”,要求输出循环左移3位后的结果，即“XYZdefabc”。是不是很简单？OK，搞定它！

解法一：

我们发现循环左移动的实质就是将字符串的左边一部分与右边一部分交换，而左边这一部分的长度为K % n，n为字符串长度。

public class Solution {
    public static String LeftRotateString(String str,int n) {
        if(str == null || str.length() == 0)
            return "";
        int len = n % str.length();
        String begin = str.substring(0, len);
        String end = str.substring(len, str.length());
        return end + begin;
    }
}

解法二：

如果不允许使用库函数呢？
可以利用翻转。由题目“翻转字符串”我们知道，I am 经翻转后变成了 am I，可以看成将字符串循环左移了，与现在的问题很相像。
假设有字符转“abcdefg”，循环左移两位 ，那么我们将左边两位翻转为ba，右边翻转为gfedc，构成了bagfedc，将该字符串翻转得到cdefgab，就是所要求的字符串。

public class Solution {
    public static String LeftRotateString(String str,int n) {
        if(str.length() == 0 || str == null)
            return str;
        char [] s = str.toCharArray();
        int len = n % str.length();
        Reverse(s, 0, len - 1);
        Reverse(s, len, str.length() - 1);
        Reverse(s, 0, str.length() - 1);
        return new String(s);
    }
    public static void Reverse(char[] str, int start, int end) {
        char tmp;
        while(start < end) {
            tmp = str[start];
            str[start] = str[end];
            str[end] = tmp;
            start++;
            end--;
        }
    }

如果题目为右移呢？只要改为右半部分翻转的长度为len就可以了。

其实这道题目解法二并没有比循环遍历数组分别记录下左右两半部分再重组左右两半部分更优。时间复杂度均为O（n），空间复杂度也均为O（n）。
但是，若将输入参数由String改为数组，则解法二的优势便体现了出来，空间复杂度只需要O（1），而遍历的空间复杂度为O（n）。