题解 | #旋转字符串#

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

方法一：暴力求解，参考河北大学一号牛客思路

求解思路
暴力求解A，将A不断地分为两部分，并且和B进行比较，只要A的两部分和B相同，则返回ture.在进行暴力求解时，首先判断A和B的长度是否相等，若不相等直接pass。

图片说明

解题代码

import java.util.*;
public class Solution {
    public boolean solve (String i, String j) {
        if(i==null||j==null||i.length()<2||j.length()<2||i.length()!=j.length())
        //首先判断A和B的长度
        {
            return false;
        }
        int x=1;
        while(x<i.length())
        {   //不断将A与B进行比较，得出结果
            String headStr = i.substring(0,x); // 头字符
            String tailStr = i.substring(x); // 尾字符
            if(j.contains(headStr)&&j.contains(tailStr)) // 判断是否包含
            {
                return true; // 返回是
            }
            x++;
        }
        return false; // 返回否
    }
}

复杂度分析
时间复杂度：一遍循环， $O(N)$
空间复杂度：对字符串A进行不断分割，使用内存空间，空间复杂度为 $O(size(A))$

方法二：优化的思想

求解思路
对于本题目的旋转字符串，我们只需要将字符串A和字符串A进行拼接，然后用字符串B和字符串A+A进行比较，如果出现相等的情况，则说明符合题意，此时输出true。（思考A+A其实构成了字符串闭环，重复两边，首尾相连，然后判断即可，这个地方多思考！！！）

图片说明

解题代码

import java.util.*;
public class Solution {
    public boolean solve (String i, String j) {
        if(i==null||j==null||i.length()<2||j.length()<2||i.length()!=j.length())
        //字符串的长度是前提，先来一个if语句
        {
            return false;
        }
        //直接判断A+A中是否有字符串B。
        return (i+i).contains(j);
    }
}

复杂度分析
时间复杂度：没有循环，时间复杂度为 $O(1)$
空间复杂度：额外引入字符串A的地址空间，空间复杂度为 $O(size(A))$