题解 | #旋转字符串#

nc114. 旋转字符串

题意

给定两字符串A和B，如果能将A从中间某个位置分割为左右两部分字符串（可以为空串），并将左边的字符串移动到右边字符串后面组成新的字符串可以变为字符串B时返回true。

1. 暴力做法

枚举A的每一位，把前半部分和后半部分拆分，再反过来连接，判断是不是等于B。

class Solution {
public:
    /**
     * 旋转字符串
     * @param A string字符串 
     * @param B string字符串 
     * @return bool布尔型
     */
    bool solve(string A, string B) {
        // x串不空，所以从1开始枚举
        for (int i = 1; i < A.size(); i++) {
            // 把A串以A[i]为界拆为 x 和 y两个子串
            string x = A.substr(0, i), y = A.substr(i);

            // 反向拼接，如能拼成B，则为true
            if (y+x == B) return true;
        }

        return false;
    }
};

时间复杂度: $O(n^2)$ . 因为要遍历n轮，每轮进行一次n长的字符串的对比，所以为 $O(n^2)$ .
空间复杂度： $O(n)$ . 定义了两个长度共计为n的变量x和y。

2. 巧妙思路

观察已知条件，可以发现，如果A和B是旋转字符串，那么一定存在一个分割点，使得在该点分割时，A串分割成X和Y两个字串，对应的B串恰好为Y和X。如下图所示：
图片说明

那么，A串自己和自己连接，就变成了XYXY, 其中一定包含子串YX。

但是如果直接这样做，会wa，因为B串有可能只有YX的一部分，或者是YXY这种。解决方法是判断下A和B长度是否相等。

class Solution {
public:
    /**
     * 旋转字符串
     * @param A string字符串 
     * @param B string字符串 
     * @return bool布尔型
     */
    bool solve(string A, string B) {
        return A.size() == B.size() && (A+A).find(B) != string::npos; // A+A中有子串B，且长度相等。
    }
};

时间复杂度: $O(n)$ . 因为相当于在长度为2n的字符串中找n长的子串，而字符串匹配算法通常时间复杂度为O(n+m), 所以总体的时间复杂度是 $O(n * 3) = O(n)$ .
空间复杂度： $O(1)$ .