旋转字符串

问题

给定一个字符串，要求把字符串前面的若干个字符移动到字符串的尾部，如把字符串“abcdef”前面的2个字符'a'和'b'移动到字符串的尾部，使得原字符串变成字符串“cdefab”
要求：时间复杂度为 O(n)，空间复杂度为 O(1)

分析

我们将整个字符串分成两部分：左侧为需要旋转的前n个字符，右侧为剩下的其余部分；借助“负负得正”的思想，处理的策略即，左右各部分独自反转字符串一次，最后统一反转处理整个字符串。

具体代码如下:

#include <iostream>
#include <String>
using namespace std;

char *reverse(char *chas, int from, int to)
{
    while(from < to)
    {
        char t = chas[from];
        chas[from++] = chas[to];
        chas[to--] = t;
    }
    cout << chas << endl;
    return chas;
}

char *rotateString(char str[], int offset, int len)
{
    if (str == NULL || len == 0)
    {
        return NULL;
    }
    reverse(str, 0, offset - 1);
    reverse(str, offset, len - 1);
    reverse(str, 0, len - 1);                                   
    return str;
}

int main(int argc, _TCHAR* argv[])
{
    char chas[] = "ABCD1234";
    int offset = 3;
    int length =  sizeof(chas) - 1;
    rotateString(chas, offset, length);
    cout << chas << endl;
    return 0;
}

上面的reverse函数利用首尾指针双指针实现。下面再看看python大法对字符串的反转：切片法，简单明了强大。

s = "hello world"
print s[::-1]