首页 > 试题广场 >

判断字符串str1是否是字符串str2的旋转词

[编程题]判断字符串str1是否是字符串str2的旋转词

热度指数：596 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

对字符串的旋转操作描述如下：

例如： str = "123456" str的所有旋转词为："123456"，"234561","345612","456123","561234","612345"。

给定两个字符串str1和str2，实现判断str1是否是str2的旋转词。

算法知识视频讲解

Ghost

源字符串×2检测子串即可。

public class Solution {
 public boolean isRotation(String str1, String str2) {
 if(str1.length() != str2.length())
 return false;
 String str = str2.concat(str2);
 return str.contains(str1);
 }
}

发表于 2015-03-09 09:04:52 回复(20)

牛客999701号

    private static bool IsReverse(string ori, string now)
        {
            char[] oriArray = ori.ToCharArray();
            char[] nowArray = now.ToCharArray();
            int length = ori.Length;
            if (length != now.Length)
            {
                return false;
            }
            int j = 0;
            int i = 0;
            for (i = 0, j = 0; j < length; ++i)
            {
                if (nowArray[0] == oriArray[i]) // 找到现在数组的第一个数对应原数组的下标
                {
                    break;
                }
            }
            if (i == length)
                return false;
            char[] newArray = new char[length];
            for (j = 0; j < length; j++)  // 把原数组排序赋值给新数组
            {
                newArray[j] = ori[i];
                ++i;
                if (i == length)
                    i = 0;
            }
            for (i = 0; i < length; i++)  // 把新数组和nowArray比较
            {
                if (newArray[i] != nowArray[i])
                {
                    return false;
                }
            }
            return true;
        }

发表于 2015-03-08 15:44:11 回复(2)

writezen

首先，@Nicholas、@Ghost、@牛客265392号童鞋的方法是最佳答案，思想完全一样。其中牛客265392号用python写是最浪的解法。@Ghost用到了java concat()返回拼接字符串，@Nicholas直接拼接简单粗暴，然后用contains()检验是否包含str1的序列，有则返回true。

这是我的解法，虽然与以上比起来不是最好的，很笨，也是可参考的V_V!我的思想就是穷举加递归。

public class Rotate {
     static boolean isRotation(String str1, String str2){
         if(str1==null||str2==null||
            str1.length()!=str2.length())
         return false;
         //拆分字符串str2
         char[] arrChar=new char[str2.length()];
         for(int i=0;i<str2.length();i++){
             arrChar[i]=str2.charAt(i);
         }
         //返回翻转校验结果
         return rotating(arrChar, str1, str2);
     }
     static boolean rotating(char[] arrChar,
                            String str1,String str2){
         //保留单词首字母
         char temp=arrChar[0];
         //开始翻转，首字母放置尾部
         for(int j=0;j<arrChar.length-1;j++){
             arrChar[j]=arrChar[j+1];
         }
         arrChar[str2.length()-1]=temp;
         //递归结束基值
         if(String.valueOf(arrChar).equals(str2))
             return false;
         //其中若果和str1相等就返回true
         if(String.valueOf(arrChar).equals(str1))
             return true;
         //返回递归校验值
         return rotating(arrChar,str1,str2); 
     }
public static void main(String[] ags){ 
     //判断给定字符串是否是某字符串的 “旋转词”
     Scanner scan=new Scanner(System.in);
     System.out.println("请输入一个字符串：");
     String str1 = scan.next();
     String str2 = scan.next();
     if(isRotation(str1, str2))
         System.out.println(str1+"是"+str2+"的旋转词！");
     else 
         System.out.println(str1+"不是"+str2+"的旋转词！");
     }
}

编辑于 2015-03-12 11:28:52 回复(2)

牛客265392号

#!/usr/bin/python

def spinStr(s1, s2):

return s2 in s1+s1

发表于 2015-03-10 17:31:08 回复(3)

5雨6

public static boolean isRotation(String str1, String str2) {
if(str1==null||str2==null){
return false;
}
if(str1.length()!=str2.length()){
return false;
}
if(str1.equals(str2)){
return true;
}
if((str1+str1).indexOf(str2)>0){
return true;
}
return false;
}

发表于 2015-03-10 16:25:28 回复(0)

赵小丽

//KMP算法

bool isRotation(string str1, string str2) {

if(str1.size()!=str2.size())

returnfalse;

if(str1.size()==0)

returntrue;

str1=str1+str1;

vector<int> nextArray=getNextArray(str2);

intsi=0;

intmi=0;

while(si<str1.size()&&mi<str2.size()){

if(str1[si]==str2[mi]){

si++;

mi++;

}

elseif(nextArray[mi]==-1)

si++;

else

mi=nextArray[mi];

}

returnmi==str2.size();

}

vector<int> getNextArray(string str){

vector<int> nextArray;

nextArray.push_back(-1);

if(str.size()==0)

returnnextArray;

nextArray.push_back(0);

intpos=2;

intcurrent=0;

while(pos<str.size()){

if(str[pos]==str[current]){

nextArray.push_back(++current);

pos++;

}

elseif(current>0)

current=nextArray[current];

else{

                nextArray.push_back(0);

pos++;

}

returnnextArray;

}

发表于 2017-05-19 16:52:04 回复(0)

JavaScript

HELLOAM

function rotate(str1,str2){

if(str1.length != str2.length){

return false;

}else{

var str3=str1+str1;

if(str3.indexOf(str2)){

return true;

}

var s1=[1,2,3,4];

var s2=[2,3,4,1];

rotate(s1,s2);

这个答应这里为什么没有js语言可以提交呢

发表于 2016-08-31 11:15:21 回复(0)

kakayang

public class Solution {
	/**
	 *	判断str1是否是str2的旋转词
	 *	输入：字符串str1，字符串str2
	 *	返回：true代表str1是str2的旋转词；false代表不是
	 */
	public boolean isRotation(String str1, String str2) {
        if(str1 == null || str2 == null)
             return false;
        if(str1.length() != str2.length())
            return false;
        if(str1.equals("") && str2.equals(""))
            return true;
        int length=str1.length();
        for(int i=0;i<length;i++)
        {
            if((str1.substring(i)+str1.substring(0, i)).equals(str2))
                return true;
        }
        return false;
	}
}

发表于 2015-10-27 11:04:48 回复(0)

Jason.Y

public class Solution {
 public int location(int length, char[] c1, char[] c2){
 for (int i = 0; i < length; i++) {
 if (c2[i] == c1[0]) {
 return i;
 }
 }
 return -1;
 }
 
 public boolean isRotation(String str1, String str2) {
 if (str1.length() != str2.length()) {
 return false;
 }
 
 int length = str1.length();
 char[] c1 = str1.toCharArray();
 char[] c2 = str2.toCharArray();
 
 int loc = location(length, c1, c2);
 if (loc == -1) {
 return false;
 }
 
 for (int i = 0; i < length; i++) {
 if (c1[i] != c2[(i+loc)%length]) {
 return false;
 }
 }
 return true;
 }
}

在IDE中没问题，但提交后是错误的，不知为何。

答案错误

"",""

输出应该为:

true

发表于 2015-03-28 01:19:30 回复(0)

GoodDemo

//利用subString函数,遍历出所有的旋转字符,放入list中 --Java

public List<String> rotateStr(String str){

List<String> list = new ArrayList<String>();
String s = "";
for(int i=0; i<str.length();i++){
s = str.substring(i, str.length())+ str.substring(0, i);
list.add(s);
}
return list;
}

发表于 2015-03-20 11:39:31 回复(0)

zhengzehuang

class Solution {
public:
/**
* 判断str1是否是str2的旋转词
* 输入：字符串str1，字符串str2
* 返回：true代表str1是str2的旋转词；false代表不是
*/
bool isRotation(string str1, string str2) {
if (str1.length() != str2.length())
{
return false;
}
string strTemp = str1 + str1;

return strTemp.find(str2) != string::npos;
}
};

发表于 2015-03-12 18:25:45 回复(0)

编号2015

扫描一次字符串即可，时间复杂度O(len),空间O(1);

for (i = 0;i<len;i++)
{
     if (str2.compare(str1.substr(i%len,len-i%len)+str1.substr(0,i%len)) == 0)
         return true;
}
return false;

编辑于 2015-03-11 13:13:15 回复(0)

Nicholas

public class test{
 public boolean IsSubset(String str1,String str2){
 if(str1.length() != str2.length())
 return false;
 String result = str1+str1;
 return result.contains(str2);
 }
 
 public static void main(String[] args){
 boolean l = new test().IsSubset("123456","234561");
 System.out.println("l = "+l);
 }
}

发表于 2015-03-10 22:18:55 回复(1)

Xoper.ducky

private static boolean isReverse(String str1,String str2){
     int length=str1.length();
     for(int i=0;i<length;i++)
     {
         if((str1.substring(i, length)+str1.substring(0, i)).equals(str2))
             return true;
     }
     return false;
 }

用substring来实现。

编辑于 2015-03-10 13:59:22 回复(1)

叶亚运

1. 如果字符串str1和字符串str2长度不等，返回false
2. 否则，分解str1和str2，为char1[]和char2[];
3. 遍历char1[], 如果存在某字符不在char2[] 中返回false, 否则返回true

发表于 2015-03-09 13:19:29 回复(1)

hello2015

1, 炸开字符串（str1 123456），存入list1，然后list1内排序（asc）==> [1,2,3,4,5,6]
2，炸开字符串（str2 216435），存入list2，然后list2内排序（asc）==> [1,2,3,4,5,6]

list1 == list2 就是了

	
		#!/usr/bin/python27
# encoding=utf-8

#把字符串拆解成list，然后进行list排序，对比list
def isReverse_a(str_a,str_b):
    if len(str_a)!=len(str_b):
        return False
    a = sorted(list(str_a))
    b = sorted(list(str_b))
    return a==b

#字符串的ascii码相乘或者相加然后对比值
def isReverse_b(str_a,str_b):
    a= reduce(lambda x,y : x+y,[ord(i) for i in list(str_a)]) 
    b= reduce(lambda x,y : x+y,[ord(i) for i in list(str_b)])
    #print a ,b, a==b
    return a==b


a = "2015,恭喜发财"
b = "恭喜发财,2015"
print isReverse_a(a,b)
print isReverse_b(a,b)

编辑于 2015-03-12 10:44:11 回复(6)

提交观点

问题信息

难度：

16条回答 11收藏 15611浏览

通过挑战的用户

wg1993

2022-06-27 19:28:03

判断字符串str1是否是字符串str2的旋转词

问题信息

热门推荐

通过挑战的用户

相关试题