首页 > 试题广场 > 翻转子串
[编程题]翻转子串
  • 热度指数:24225 时间限制:C/C++ 3秒,其他语言6秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解

假定我们都知道非常高效的算法来检查一个单词是否为其他字符串的子串。请将这个算法编写成一个函数,给定两个字符串s1和s2,请编写代码检查s2是否为s1旋转而成,要求只能调用一次检查子串的函数。

给定两个字符串s1,s2,请返回bool值代表s2是否由s1旋转而成。字符串中字符为英文字母和空格,区分大小写,字符串长度小于等于1000。

测试样例:
"Hello world","worldhello "
返回:false
"waterbottle","erbottlewat"
返回:true
思路

以s1=ABCD为例,我们先分析s1进行循环移位之后的结果:
ABCD->BCDA->CDAB->DABC->ABCD  .......
假设我们把前面移走的数据进行保留:
ABCD->ABCDA->ABCDAB->ABCDABC->ABCDABCD.....
因此看出,对s1做循环移位,所得字符串都将是字符串s1s1的子字符串。如果s2可以由s1循环移位得到,则一定可以在s1s1上。

代码
class ReverseEqual {
public:
    bool checkReverseEqual(string s1, string s2) {
        int size1 = s1.size();
        int size2 = s2.size();
        if(size1 == 0 || size2 == 0){
            return false;
        }//if
        string str = s1 + s1;
        if(str.find(s2) == -1){
            return false;
        }//if
        return true;
    }
};


发表于 2015-08-19 19:25:22 回复(28)
String temp = s1 + s1;
return temp.contains(s2);

发表于 2016-03-27 19:36:17 回复(10)
//根据置顶的那位同学的思路写的
import java.util.*;

public class ReverseEqual {
   public boolean checkReverseEqual(String s1, String s2) {
        // write code here
        if(s1.length()==0||s2.length()==0||s1.length()!=s2.length()){
        	return false;
        }
		String tem=s1+s1;
        if(tem.contains(s2)){
        	return true;
        }
        return false;
       
    }
}

发表于 2016-08-20 10:10:51 回复(1)
思路:s1拼接自己一次当作s3,s2如果是s1旋转来的就必定是s3的子串
发表于 2016-02-27 16:35:37 回复(0)
if (s1.length()!=s2.length()) {
	return false;
}
String str=s2+s2;
if (str.contains(s1)) {
	return true;
}else {
	return false;
}
这其实是一种偷巧的方法,还有数组排序的方法也是
发表于 2015-10-27 15:18:52 回复(1)

Python one line solution:

return set(s1)==set(s2)
发表于 2017-10-01 20:19:58 回复(2)
看了评论才知道题目意思,对不起语文老师,话说我是来找茬的,我把它当初前面一题,两个字符串异序同构做的,竟然AC了,这测试用例,已提交纠错了,不过话说我已纠错了不下好几题了,至今没有得到反馈啊,不知道是不是我太菜,大神没空搭理我,让我哭会,

//能AC的错误代码
 public boolean checkReverseEqual(String s1, String s2) {
        if(s1==null||s2==null) return false;
        if(s1.length()!=s2.length()) return false;
        int[] hash1=new int[256];
        int[] hash2=new int[256];
        for(int i=0;i<s1.length();i++){
            hash1[s1.charAt(i)]++;
            hash2[s2.charAt(i)]++;
        } 
        for(int j=0;j<hash1.length;j++) if(hash1[j]!=hash2[j]) return false;
        return true;
    }

//正确代码 方法一
public boolean checkReverseEqual(String s1, String s2) {
        if(s1==null||s2==null) return false;
        if(s1.length()!=s2.length()) return false;
        s1=s1+s1;
        return s1.indexOf(s2)==-1?false:true;
    }
//同上,方法二 自己写匹配部分
public boolean checkReverseEqual(String s1, String s2) {
        if(s1==null||s2==null) return false;
        if(s1.length()!=s2.length()) return false;
        s1+=s1;
        int count=0;
        for(int i=0;i<s1.length()&&count<s2.length();i++){
            if(s2.charAt(count)==s1.charAt(i)) count++;
            else count=0;
        }
        return count==s2.length()?true:false;
    }

编辑于 2017-05-11 19:24:07 回复(3)
import java.util.*;
//本来想用kmp匹配的,但是太难了,写不出来
public class ReverseEqual {
    public boolean checkReverseEqual(String s1, String s2) {
       if(s1.length()!=s2.length())
           return false;
        String str=s1+s1;
        if(str.contains(s2))
            return true;
        return false;
    }
}

发表于 2017-02-22 21:44:47 回复(1)
使用KMP算法实现子字符串是否存在判断
import java.util.*;

public class ReverseEqual {
    public boolean checkReverseEqual(String s1, String s2) {
        // write code here
         int len1=s1.length();
       int len2=s2.length();
       if(len1!=len2)
           return false;
       if(len1<1)
           return true;
       String str=s1+s1;
       int []next=getNext(s2);
       int len=str.length();
       int j=0;
       for(int i=0;i<len;i++){
           if(j>0&&str.charAt(i)!=s2.charAt(j))
               j=next[j];
           if(str.charAt(i)==s2.charAt(j))
               j++;
           if(j==s2.length()){
               return true;
           }
       }
       return false;
    }
    int[] getNext(String str){
        int len=str.length();
       int [] next=new int[len+1];
       int j=0;
       next[0]=next[1]=0;
       for(int i=1;i<len;i++){
           if(j>0&&str.charAt(i)!=str.charAt(j))
               j=next[j];
           if(str.charAt(i)==str.charAt(j))
               j++;
           next[i+1]=j;
       }
       return next;
    }
}

发表于 2015-09-30 19:04:39 回复(2)
#if 1
bool checkReverseEqual(string s1, string s2) 
{
	// write code here
	if (s1.size() != s2.size())
		return false;
	string str = s1+s1;
	int pos = str.find(s2);
	if (pos != string::npos)
		return true;
	return false;
}
#endif

发表于 2017-04-18 12:28:03 回复(0)
class ReverseEqual {
public:
    bool checkReverseEqual(string s1, string s2) {
        if(s1.size() != s2.size()) return false;
        int siz = s1.size();
        for(int i = 0; i < siz; i++){
            if(s1[0] == s2[i]){
                int pos1 = 0, pos2 = i, count = 0;
                while(pos1 < siz && s1[pos1] == s2[pos2]){
                    count++;
                    pos1++;
                    if(pos2 == siz -1) pos2 = 0;
                    else pos2++;
                }
                if(count == siz) return true;
            }
        }
        
        return false;
    }
};

发表于 2016-05-05 16:57:04 回复(0)

public static boolean check(String s1, String s2) {

        // write code here

char[]ca=s1.toCharArray();

char[]cb=s2.toCharArray();

Arrays.sort(ca);

Arrays.sort(cb);

return Arrays.equals(ca,cb);

    }


发表于 2016-04-20 21:26:11 回复(2)
import java.util.*;

public class ReverseEqual {
    public boolean checkReverseEqual(String s1, String s2) {
        if (s1.length() != s2.length())
			return false;
		if (s1.equals(s2))
			return true;
		int len = s1.length();
		int offset = 1;
		int j = 0;
		while (offset < len) {
			while (offset < len && !s1.substring(0, offset).equals(
					s2.substring(len - offset))){
				offset++;
			}
				
			if (offset < len
					&& s1.substring(offset)
							.equals(s2.substring(0, len-offset))) {
				return true;
			}
			offset++;
		}
		return false;
    }
}

发表于 2016-03-03 22:11:33 回复(0)
依然是异或
public boolean checkReverseEqual(String s1, String s2) {
        // write code here
        char[] strs1=s1.toCharArray();
        char[] strs2=s2.toCharArray();
        if(strs1.length==strs2.length){
            int flag=(int)strs1[0]^(int)strs2[0];
            for(int i=1;i<strs1.length;i++){
                flag^=(int)strs1[i]^(int)strs2[i];
            }
            if(flag==0){
                return true;
            }
        }
        return false;
    }

发表于 2019-09-06 14:07:37 回复(0)
class ReverseEqual {
public:
    bool checkReverseEqual(string s1, string s2) {
        // write code here
        if(s1.size() != s2.size()) return false;
        int n = s1.size();

        int s = 0, l = n - s;
        while (n - l <= n){
            if(s1 == s2.substr(s,l) + s2.substr(0,n-l))
                return true;
            s ++;
            l = n - s;
        }
        return false;
    }
};
//我的low解法

发表于 2019-06-10 13:46:41 回复(0)
用Python刷题感觉在开挂

# -*- coding:utf-8 -*-
class ReverseEqual:
    def checkReverseEqual(self, s1, s2):
        return s2 in s1 * 2

发表于 2018-12-26 11:52:31 回复(0)
import java.util.*;

public class ReverseEqual {
    public boolean checkReverseEqual(String s1, String s2) {        StringBuilder builder = null;
        int length = s1.length();
        boolean flag = false;
        for(int i=1;i<length;i++){
            builder = new StringBuilder();
            builder.append(s1.substring(i,length)).append(s1.substring(0,i));
            if(builder.toString().equals(s2)){
                flag = true;
                break;
            }
        }
        return flag;
    }
}


编辑于 2017-10-06 10:18:08 回复(0)
是不是有这样的题才会让大家掏尽心机
        return (s2+s2).contains(s1);

发表于 2017-07-28 21:59:01 回复(0)
public static boolean checkReverseEqual(String s1, String s2) {
        char[] ch1 = s1.toCharArray();
        char[] ch2 = s2.toCharArray();
        if(ch1.length!=ch2.length){
        return false;
        }
        boolean bo = false;
        char x = ch1[0];
        for(int j=0;j<ch1.length;j++){
        String s ="";
//如果有一个元素和s1中第一个元素相等,则从它开始写一个新字符串 判断和s1是否相等
        if(ch2[j]==x){
        for(int i=j;i<ch1.length;i++){
        s = s+ch2[i];
        }
        for(int i=0;i<j;i++){
        s = s+ch2[i];
        }
        }
        if(s1.equals(s)){
        bo = true;
        break;
        }else{
        continue;
        }
       
        }
        return bo;
    }
编辑于 2017-04-25 17:46:01 回复(0)

class ReverseEqual {
public:
    bool checkReverseEqual(string s1, string s2) {
        // write code here
        string str;
        str+=s1;str+=s1;
    if(str.find(s2)!=std::string::npos)
        return true;
        else
            return false;
    }
};
发表于 2017-04-20 21:49:11 回复(0)