字符串旋轉算法詳解：暴力移位 vs 三步翻轉法（附 C++ 實現）

問題描述

給定字符串 s 長度 n，將前 m 個字符移至尾部。例："abcdef"，m=3 → "defabc"。

方法一：暴力單步移位 O(n×m)

重複 m 次：取首字符，前移 n-1 字符，首字符放尾部。

void LeftShiftOne(char* s, int n) {
    char t = s[0];
    for (int i = 1; i < n; ++i) s[i-1] = s[i];
    s[n-1] = t;
}
void LeftRotateString(char* s, int n, int m) {
    while (m--) LeftShiftOne(s, n);
}

缺點：m 大時極慢，O(n×m) 時間複雜度。

方法二：三步翻轉法 O(n)

將字符串視為兩部分 A(前 m) 和 B(後 n-m)：

1. 翻轉 A → Aᵀ
2. 翻轉 B → Bᵀ
3. 整體翻轉 (Aᵀ Bᵀ)ᵀ = B A

例："abcdef"，m=3
A="abc" → "cba"
B="def" → "fed"
"cbafed" → "defabc" ✓

void ReverseString(char* s, int from, int to) {
    while (from < to) {
        char t = s[from];
        s[from++] = s[to];
        s[to--] = t;
    }
}
void LeftRotateString(char* s, int n, int m) {
    m %= n;                    // 處理 m ≥ n
    ReverseString(s, 0, m-1);
    ReverseString(s, m, n-1);
    ReverseString(s, 0, n-1);
}

複雜度對比

進階變體

• 右旋：m = n - m 再左旋，或對稱三步翻轉。
• STL 實現：std::rotate(s, s+m, s+n) 內部即三步翻轉。
• 塊交換算法：遞歸交換等長塊，同 O(n) 但常數較大。

總結

字符串旋轉是經典算法面試題，三步翻轉法以簡潔優雅的 O(n) 原地解法廣為人知。理解其「分治+對稱」思想，有助於掌握更多陣列/字符串原地變換技巧。