题解 | 旋转字符串（C++版本）

描述：
给定两字符串A和B，如果能将A从中间某个位置分割为左右两部分字符串（可以为空串），并将左边的字符串移动到右边字符串后面组成新的字符串可以变为字符串B时返回true。
例如：如果A=‘youzan’，B=‘zanyou’，A按‘you’‘zan’切割换位后得到‘zanyou’和B相同，返回true。
再如：如果A=‘abcd’，B=‘abcd’，A切成‘abcd’和''（空串），换位后可以得到B，返回true。

题意分析：
根据题意，可以得到两个隐含的条件：

• 字符串A被分割重组后要得到字符串B，可以得到如果A和B的长度不一致，一定会返回false。
• 因为字符串A分割后子字符串可以为空串，这可以得到如果A==B，那么一定返回true。

方法一：暴力破解法
这里最直观的解法就是，每次将字符串A数组的第一个字符旋转到整个字符串的末尾，然后与字符串B进行比较。
具体解法参见如下动图：

class Solution {
public:
    /**
     * 旋转字符串
     * @param A string字符串 
     * @param B string字符串 
     * @return bool布尔型
     */
    //将字符串A数组的第一个字符旋转到整个字符串的末尾
    void rotateOnce(string & str)
    {
        string tmp(str,1);
        str = tmp + str[0];
    }

    bool solve(string A, string B) 
    {
        //A和B长度不等，无论A怎么分割重组一定不能得到B
        if(A.size()!=B.size()) return false;
        //A可以分割为其本身和空串，所以A==B时一定返回true
        if(A==B) return true;

        string rotatedstr=A;
        //如果字符串长度为n，那么调用rotateOnce函数n次得到的是原数组，
        //所以只用调用该函数n-1次即可。
        for(int i=0;i<A.size()-1;i++)
        {
            rotateOnce(rotatedstr);
            if(rotatedstr==B)
                return true;
        }

        return false;
    }
};

复杂度分析：

• 时间复杂度：rotateOnce函数的执行时间为 ，调用了n次，所以本段代码的时间复杂度为 ;
• 空间复杂度：除了申请rotatedstr和tmp这两个变量外没有再申请别的空间，所以空间复杂度为 。

方法二：子字符串查找法
由方法一进行扩展：将A+A构成一个字符串，那么该字符串一定包含了A所有旋转后的结果，如果B是拼接后字符串的子字符串，那么一定会有A分割重组后的字符串等于B。

对于查找子串，这里使用find()进行查找。find函数返回子字符串在主串中的位置，如果没有找到，则返回-1。

class Solution {
public:
    /**
     * 旋转字符串
     * @param A string字符串 
     * @param B string字符串 
     * @return bool布尔型
     */
    bool solve(string A, string B) 
    {
            //A和B长度不等，无论A怎么分割重组一定不能得到B
            if(A.size()!=B.size()) return false;
            //A可以分割为其本身和空串，所以A==B时一定返回true
            if(A==B) return true;

            string str=A+A;
            if(str.find(B)!=-1) return true;
            else return false;
    }
};

复杂度分析：

• 时间复杂度：整个代码运行过程中，时间上的开销主要集中在find()函数这里，查阅资料得到，find()函数采用的是朴素匹配算法，所以平均时间复杂度为 ;
• 空间复杂度：除了申请str变量外没有再申请别的空间，所以空间复杂度为 。