题解 | #左旋转字符串#

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

方法一：拼接法
核心思想：
        根据给定的字符串，需要向左移动K位(K小于等于字符串S的长度)，获取移位后的字符串。可以将字符串拷贝一份拼接在原字符串上。则左移后，从左移的位数开始截取长度为len的子字符串即可得到结果。
边界情况：字符串为空的时候，结果直接返回空。

图解：

核心代码：

string LeftRotateString(string str, int n) {
    if(str.size()==0)
        return "";
    int len = str.size();
    str+=str;             //拼接为两个字符串
    return str.substr(n%len,len);
}

时间复杂度O(n) //substr的时间复杂度跟获取的字符串长度有关
空间复杂度O(n)

方法二：三次翻转
核心思想：
        408考研的初试题运用了三次翻转的思想实现字符串左移，这种思想刚好可以运用到此题中。这种方式比较有技巧性，从左移的K位将字符串划分为两部分子字符串，然后分别对两部分子字符串进行翻转，最后对整体字符串进行翻转得到左移的效果。题意可知需要移动K位，则三次左移如下：
1）翻转前K个字符
2）翻转后N-K个字符
3）翻转整个字符串

图解：

核心代码：

string LeftRotateString(string str, int n) {
    reverse(str.begin(), str.begin()+n);   //第一次翻转
    reverse(str.begin()+n, str.end());     //第二次翻转
    reverse(str.begin(), str.end());      //第三次翻转
    return str;
}

时间复杂度O(n)
空间复杂度O(1)