剑指offer43 左旋转字符串

剑指offer43

左旋转字符串

题目描述

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

输入

“abcXYZdef”,3

输出

“XYZdefabc”

思路

例字符串：abcdefg, n=5,

输出结果应为：fgabcde

反转过程如下：

第一次：反转0-4（n-1）位的字符，结果为：edcbafg

第二次：反转剩下(n,length-1)的字符，结果为：edcbagf

第三次：整体反转(0,length-1)，结果为：fgabcde

代码

public class Solution {
    public String LeftRotateString(String str,int n) {
        char[] chars = str.toCharArray();
        if(chars.length<n) return str;
        reverse(chars, 0, n-1);
        reverse(chars, n, chars.length-1);
        reverse(chars, 0, chars.length-1);
        StringBuilder sb = new StringBuilder(chars.length);
        for(char c:chars){
            sb.append(c);
        }
        return sb.toString();
    }

    //反转函数
    public static void reverse(char[] chars, int low, int high){
        char temp;
        while(low<high){
            temp = chars[low];
            chars[low] = chars[high];
            chars[high] = temp;
            low++;
            high--;
        }
    }
}

/**
例字符串：abcdefg, n=5, 输出结果应为：fgabcde
反转过程如下：
第一次：反转0-4（n-1）位的字符，结果为：edcbafg
第二次：反转剩下(n,length-1)的字符，结果为：edcbagf
第三次：整体反转(0,length-1)，结果为：fgabcde
**/

扩展：字符串移位包含的问题

题目描述

给定两个字符串S1， S2，要求判定S2是否能够被S1做循环移位（rotate）得到的字符串所包含。

输入

“AABCD” “CDAA”

输出

true

解题思路

可以对循环移位之后的结果进行分析。

以S1=ABCD为例，先分析S1循环移位后的结果，如下：

ABCD–BCDA–CDAB–DABC–ABCD

假设我们把前面移除的数据保留，有如下规律：

ABCD–ABCDA–ABCDAB–ABCDABC–ABCDABCD

因此，对S1做循环移位得到的字符串是S1S1的子字符串，如果结果为true,那么S2一定包含在S1S1中。依次遍历S1S1即可。