> For the complete documentation index, see [llms.txt](https://aaronice.gitbook.io/lintcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://aaronice.gitbook.io/lintcode/problem-solving-summary/string-rotation.md).

# String or Array Rotation

## 字符串、数组的反转、逆序问题

### 三步翻转法

将一个字符串分成`X`和`Y`两个部分，在每部分字符串上定义反转操作，如`X^T`，即把X的所有字符反转（如，`X="abc"`，那么`X^T="cba"`），那么就得到下面的结论：`(X^TY^T)^T=YX`，显然就解决了字符串的反转问题。

例如，字符串 `"abcdef"` ，若要让`"def"`翻转到`"abc"`的前头，只要按照下述3个步骤操作即可：

1. 首先将原字符串分为两个部分，即`X: "abc"`，`Y: "def"`；
2. 将`X`反转，`X -> X^T`，即得：`abc -> cba`；将`Y`反转，`Y -> Y^T`，即得：`def -> fed`。
3. 反转上述步骤得到的结果字符串`X^TY^T`，即反转字符串`cbafed`的两部分（`cba`和`fed`）给予反转，`cbafed`得到`defabc`，形式化表示为`(X^TY^T)^T=YX`，这就实现了整个反转。

<https://segmentfault.com/a/1190000002694646>

<https://blog.csdn.net/u010016196/article/details/45126853>

**Array Rotate Template**

```java
// 3-step reverse - O(n) time, O(1) space
class Solution {
    public void rotateRight(int[] nums, int k) {
        int n = nums.length;
        k = k % n; 
        reverse(nums, 0, n - k - 1);
        reverse(nums, n - k, n - 1);
        reverse(nums, 0, n - 1);
    }
    public void rotateLeft(int[] nums, int k) {
        int n = nums.length;
        k = k % n;
        reverse(nums, 0, n - k - 1);
        reverse(nums, n - k, n - 1);
        reverse(nums, 0, n - 1);
    }
    private void reverse(int[] nums, int s, int t) {
        while (s < t) {
            int tmp = nums[s];
            nums[s] = nums[t];
            nums[t] = tmp;
            s++;
            t--;
        }
    }
}
```

#### 相关问题：

[Rotate Array](https://leetcode.com/problems/rotate-array/) - [Solution](https://leetcode.com/problems/rotate-array/solution/)