LeetCode解题报告（26）-- 796. Rotate String

Problem

We are given two strings, A and B.

A shift on A consists of taking string A and moving the leftmost character to the rightmost position. For example, if A = 'abcde', then it will be 'bcdea' after one shift on A. Return True if and only if A can become B after some number of shifts on A.

Example 1:

1 2	Input: A = 'abcde', B = 'cdeab' Output: true

Example 2:

1 2	Input: A = 'abcde', B = 'abced' Output: false

Analysis

这道题涉及到的是字符串移位的操作。难点在于这种移位是循环的移位，所以我们要考虑到尾部的赋值问题。基本的思路是：对原字符串A，输出结果B，B先从头i = 0开始，一直赋值到i = size - shift，然后再用另一个变量j = 0从A的头开始接着赋值给B[i]，直到j = shift。

Solution

使用两个循环即可实现上述操作了，注意下下标的边界问题和空字符串问题即可。

Code

class Solution {
public:
    bool rotateString(string A, string B) {
        if (A.size() == 0 && B.size() == 0)
            return true;
        int size = A.size();
        for (int shift = 0; shift < size; shift++) {
            string str = rotate(A, shift);
            if (str == B) {
                return true;
            }
        }
        return false;
    }
    string rotate(string A, int shift) {
        string output = A;
        int size = A.size();
        int index = 0;
        for (int i = 0; i < size; i++) {
            if (i < size - shift) {
                output[i] = A[i + shift];
            }
            else {
                output[i] = A[index];
                index++;
            }
        }
        return output;
    }
};

运行时间：约0ms，超过100%的CPP代码。

Summary

这道题实现起来难度不大，只要自己在纸上演算几次就能找到规律。最近刚好在写DES算法，其中也用到了循环左移的操作，因此这个算法在数据加密的领域非常常见，因此我认为值得与大家分享。本题的分析到这里，谢谢您的支持！