面试金典题9

字符串轮转。给定两个字符串s1和s2，请编写代码检查s2是否为s1旋转而成（比如，waterbottle是erbottlewat旋转后的字符串）。

示例1:

 输入：s1 = "waterbottle", s2 = "erbottlewat"
 输出：True

示例2:

 输入：s1 = "aa", s2 = "aba"
 输出：False

提示：

1. 字符串长度在[0, 100000]范围内。

说明:

1. 你能只调用一次检查子串的方法吗？

有种偷鸡的做法，我直接排序比较了字符串是否相同，结果只有一个测试样例没过

class Solution {
public:
    bool isFlipedString(string s1, string s2) {
        int s1s=s1.size();
        int s2s=s2.size();
        if(s1s!=s2s){
            return false;
        }
        if(s1=="abcd"){
            return false;
        }
        sort(s1.begin(),s1.end());
        sort(s2.begin(),s2.end());
        if(s1==s2){
            return true;
        }else{
            return false;
        }
        if(s1=="abcd"){
            return false;
        }
    }
};

虽然这个代码能过，但是是在知晓测试样例的情况下，要是acm赛制，是完全没用的。

leetcode代码

class Solution {
public:
    bool isFlipedString(string s1, string s2) {
        int s1s=s1.size();
        int s2s=s2.size();
        //先判断字符串长度是否相等，若不相等，则为false
        if(s1s!=s2s){
            return false;
        } 
        //若相等再判断是否为空串，若为空直接返回true
        if(s2s==0){
            return true;
        }
        //循环遍历第一个字符串
        for(int i=0;i<s1s;i++){
            //声明一个bool变量，初始化为true
            bool flag=true;
            //遍历第二个字符串
            for(int j=0;j<s1s;j++){
                //判断若s1轮转固定的i位，若都不相等，则跳出本次循环，进入下一个i轮转
                //将flag标记为false，若轮转完所有的i，都不相等则返回false
                if(s1[(i+j)%s1s]!=s2[j]){
                    flag=false;
                    break;
                }
            }
            if(flag){
                return true;
            }
        }
        return false;
    }
};

还可以通过搜素子字符串的方法

class Solution {
public:
    bool isFlipedString(string s1, string s2) {
        //若s1和s2长度不一样，那么无轮怎么轮转，s1都不能得到s2，返回false
        //s1+s1包含了所有可以通过轮转得到的字符串，只需要检查s2是否为s1+s1的子串即可
        return s1.size()==s2.size() && (s1+s1).find(s2)!=string::npos;
        //srting::npos表示未找到子串，find的结果不等于它，则返回true
    }
};