Rotate String

https://www.lintcode.com/problem/rotate-string/description

Description

Given a string and an offset, rotate string by offset. (rotate from left to right)

Have you met this question in a real interview?

Yes

Problem Correction

Example

Given"abcdefg".

offset=0 => "abcdefg"
offset=1 => "gabcdef"
offset=2 => "fgabcde"
offset=3 => "efgabcd"

Challenge

Rotate in-place with O(1) extra memory.

Analysis

Solution

三步翻转法 O(n) time, O(1) sapce

/**
* This reference program is provided by @jiuzhang.com
* Copyright is reserved. Please indicate the source for forwarding
*/

public class Solution {
    /**
     * @param str: an array of char
     * @param offset: an integer
     * @return: nothing
     */
    public void rotateString(char[] str, int offset) {
        // write your code here
        if (str == null || str.length == 0)
            return;

        offset = offset % str.length;
        reverse(str, 0, str.length - offset - 1);
        reverse(str, str.length - offset, str.length - 1);
        reverse(str, 0, str.length - 1);
    }

    private void reverse(char[] str, int start, int end) {
        for (int i = start, j = end; i < j; i++, j--) {
            char temp = str[i];
            str[i] = str[j];
            str[j] = temp;
        }
    }
}

public class Solution {
    /**
     * @param str: An array of char
     * @param offset: An integer
     * @return: nothing
     */
    public void rotateString(char[] str, int offset) {
        if(str.length <=0)
            return;
        offset = offset % str.length;
       char[] str1 = new char[str.length + offset];
        for(int i = str1.length-1;i>= offset; i--){
            str1[i] = str[i - offset];
        }

        for(int i = 0; i< offset; i++){
            str1[i] = str1[i+str.length];
        }
        for(int i = 0; i< str.length; i++){
            str[i] = str1[i];
        }
    }
}