Rotate String

Question

  1. Given a string and an offset, rotate string by offset. (rotate from left to right)
  3. Example
  4. Given "abcdefg"
  6. for offset=0, return "abcdefg"
  8. for offset=1, return "gabcdef"
  10. for offset=2, return "fgabcde"
  12. for offset=3, return "efgabcd"
  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
  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]
  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.         }
  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.     }
  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.         }
  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);
  18.         return A;
  19.     }
  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