Rotate String
最后更新于：2022-04-02 01:07:44
# Rotate String
### Source
- lintcode: [(8) Rotate String](http://www.lintcode.com/en/problem/rotate-string/)
~~~
Given a string and an offset, rotate string by offset. (rotate from left to right)
Example
Given "abcdefg"
for offset=0, return "abcdefg"
for offset=1, return "gabcdef"
for offset=2, return "fgabcde"
for offset=3, return "efgabcd"
...
~~~
### 题解
常见的翻转法应用题，仔细观察规律可知翻转的分割点在从数组末尾数起的offset位置。先翻转前半部分，随后翻转后半部分，最后整体翻转。
### Python
~~~
class Solution:
"""
param A: A string
param offset: Rotate string with offset.
return: Rotated string.
"""
def rotateString(self, A, offset):
if A is None or len(A) == 0:
return A
offset %= len(A)
before = A[:len(A) - offset]
after = A[len(A) - offset:]
# [::-1] means reverse in Python
A = before[::-1] + after[::-1]
A = A[::-1]
return A
~~~
### C++
~~~
class Solution {
public:
/**
* param A: A string
* param offset: Rotate string with offset.
* return: Rotated string.
*/
string rotateString(string A, int offset) {
if (A.empty() || A.size() == 0) {
return A;
}
int len = A.size();
offset %= len;
reverse(A, 0, len - offset - 1);
reverse(A, len - offset, len - 1);
reverse(A, 0, len - 1);
return A;
}
private:
void reverse(string &str, int start, int end) {
while (start < end) {
char temp = str[start];
str[start] = str[end];
str[end] = temp;
start++;
end--;
}
}
};
~~~
### Java
~~~
public class Solution {
/*
* param A: A string
* param offset: Rotate string with offset.
* return: Rotated string.
*/
public char[] rotateString(char[] A, int offset) {
if (A == null || A.length == 0) {
return A;
}
int len = A.length;
offset %= len;
reverse(A, 0, len - offset - 1);
reverse(A, len - offset, len - 1);
reverse(A, 0, len - 1);
return A;
}
private void reverse(char[] str, int start, int end) {
while (start < end) {
char temp = str[start];
str[start] = str[end];
str[end] = temp;
start++;
end--;
}
}
};
~~~
### 源码分析
1. 异常处理，A为空或者其长度为0
1. `offset`可能超出A的大小，应模`len`后再用
1. 三步翻转法
Python 虽没有提供字符串的翻转，但用 slice 非常容易实现，非常 Pythonic!
### 复杂度分析
翻转一次时间复杂度近似为 O(n)O(n)O(n), 原地交换，空间复杂度为 O(1)O(1)O(1). 总共翻转3次，总的时间复杂度为 O(n)O(n)O(n), 空间复杂度为 O(1)O(1)O(1).
### Reference
- [Reverse a string in Python - Stack Overflow](http://stackoverflow.com/questions/931092/reverse-a-string-in-python)
';