Rotate String

Question

• lintcode: (8) Rotate String

  1. Given a string and an offset, rotate string by offset. (rotate from left to right)
     2. 3. Example
     3. Given "abcdefg"
     4. 6. for offset=0, return "abcdefg"
     5. 8. for offset=1, return "gabcdef"
     6. 10. for offset=2, return "fgabcde"
     7. 12. for offset=3, return "efgabcd"
     8. 14. ...

題解

常見的翻轉法應用題，仔細觀察規律可知翻轉的分割點在從數組末尾數起的offset位置。先翻轉前半部分，隨後翻轉後半部分，最後整體翻轉。

Python

  1. class Solution:
    2.     """
    3.     param A: A string
    4.     param offset: Rotate string with offset.
    5.     return: Rotated string.
    6.     """
    7.     def rotateString(self, A, offset):
    8.         if A is None or len(A) == 0:
    9.             return A
    10.   11.         offset %= len(A)
    12.         before = A[:len(A) - offset]
    13.         after = A[len(A) - offset:]
    14.         # [::-1] means reverse in Python
    15.         A = before[::-1] + after[::-1]
    16.         A = A[::-1]
    17.   18.         return A

C++

  1. class Solution {
    2. public:
    3.   /**
    4.      * param A: A string
    5.      * param offset: Rotate string with offset.
    6.      * return: Rotated string.
    7.      */
    8.     string rotateString(string A, int offset) {
    9.         if (A.empty() || A.size() == 0) {
    10.             return A;
    11.         }
    12.   13.         int len = A.size();
    14.         offset %= len;
    15.         reverse(A, 0, len - offset - 1);
    16.         reverse(A, len - offset, len - 1);
    17.         reverse(A, 0, len - 1);
    18.         return A;
    19.     }
    20.   21. private:
    22.     void reverse(string &str, int start, int end) {
    23.         while (start < end) {
    24.             char temp = str[start];
    25.             str[start] = str[end];
    26.             str[end] = temp;
    27.             start++;
    28.             end--;
    29.         }
    30.     }
    31. };

Java

  1. public class Solution {
    2.     /*
    3.      * param A: A string
    4.      * param offset: Rotate string with offset.
    5.      * return: Rotated string.
    6.      */
    7.     public char[] rotateString(char[] A, int offset) {
    8.         if (A == null || A.length == 0) {
    9.             return A;
    10.         }
    11.   12.         int len = A.length;
    13.         offset %= len;
    14.         reverse(A, 0, len - offset - 1);
    15.         reverse(A, len - offset, len - 1);
    16.         reverse(A, 0, len - 1);
    17.   18.         return A;
    19.     }
    20.   21.     private void reverse(char[] str, int start, int end) {
    22.         while (start < end) {
    23.             char temp = str[start];
    24.             str[start] = str[end];
    25.             str[end] = temp;
    26.             start++;
    27.             end--;
    28.         }
    29.     }
    30. };

源碼分析

1. 異常處理，A為空或者其長度為0
2. offset可能超出A的大小，應對len取餘數後再用
3. 三步翻轉法

Python 雖沒有提供字符串的翻轉，但用 slice 非常容易實現，非常 Pythonic!

複雜度分析

翻轉一次時間複雜度近似為 O(n), 原地交換，空間複雜度為 O(1). 總共翻轉3次，總的時間複雜度為 O(n), 空間複雜度為 O(1).

Reference

• Reverse a string in Python - Stack Overflow