首页 > 试题广场 >

旋转字符串

[编程题]旋转字符串

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

字符串旋转:

给定两字符串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字符串长度满足 $n \le 1000$ ，保证字符串中仅包含小写英文字母和阿拉伯数字

进阶：时间复杂度 $O(n)$ ，空间复杂度 $O(n)$

示例1

输入

"youzan","zanyou"

输出

true

示例2

输入

"youzan","zyouan"

输出

false

示例3

输入

"nowcoder","nowcoder"

输出

true

算法知识视频讲解

牛呀牛呀~

用JS的方法

function solve( A , B ) {
for(let i = 1; i < A.length; i++){
var str1 = A.slice(0,i);
var str2 = A.slice(i,A.length);
var newstr = str2+str1;
if(newstr == B){
return true
}
}
return false
}

发表于 2021-04-16 16:30:42 回复(0)

F10q

class Solution {
public:
    /**
     * 旋转字符串
     * @param A string字符串 
     * @param B string字符串 
     * @return bool布尔型
     */
    bool solve(string A, string B) {
        // write code here
        for(int i=0;i<A.size()-1;i++)
        {
            if(A.substr(i,A.size()-i)+A.substr(0,i)==B){
                return true;
            }
     
        }
        return false;
    }
};

发表于 2020-08-08 12:28:02 回复(0)

爱吃pai的e

看其他人的思路：

每次从str前面抽取一个，放在后面，比较两个是否相等

public boolean checkStr(String str, String target){
    // 边界值
    if (str == null) return ;
    for (int i = 0; i < str.length()l;++i){
        if (str.equals(target)) return true;
        // 拆分比较，每次从头部拿出一个，放在后面
        str =  str.subString(1) + str.subString(0,1);
    }
    return false;
}
// 如果有问题，欢迎指正！

编辑于 2020-08-06 19:00:43 回复(0)

苏沐沐橙

public class Solution {
    public boolean solve (String A, String B) {
        if(A.length()!=B.length()) return false;
        return (A+A).contains(B);
    }
}

发表于 2020-08-14 17:07:55 回复(1)

牛客828692697号

public class Solution {
public boolean solve (String A, String B) {
if(A.length()!=B.length()) return false;
return (A+A).contains(B);
}
}

发表于 2020-08-19 12:09:38 回复(0)

C++

v小罗同学

class Solution {
public:
    /**
     * 旋转字符串
     * @param A string字符串 
     * @param B string字符串 
     * @return bool布尔型
     */
    bool solve(string A, string B) {
        return A.size() == B.size() && (A + A).find(B) != -1;
    }
};

发表于 2021-09-11 22:30:43 回复(1)

Java

我迪迦在东北

import java.util.*;


public class Solution {
    /**
     * 旋转字符串
     * @param A string字符串 
     * @param B string字符串 
     * @return bool布尔型
     */
    public boolean solve (String A, String B) {
        // write code here
        return A.length()==B.length()&&(A+A).contains(B);
    }
}

发表于 2021-08-19 15:36:31 回复(3)

C++

zkingcode

class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 旋转字符串
     * @param A string字符串
     * @param B string字符串
     * @return bool布尔型
     */
    bool solve(string A, string B) {
        string c = B + B;
        return (A.size() == B.size()) and (c.find(A) != -1);
    }
};

发表于 2024-04-10 11:07:20 回复(0)

苦行潜修者

using System;

using System.Collections.Generic;

class Solution {

/**

* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可

* 旋转字符串

* @param A string字符串

* @param B string字符串

* @return bool布尔型

public bool solve (string A, string B) {

// write code here

if (string.IsNullOrWhiteSpace(B))

return true;

if (string.IsNullOrWhiteSpace(A) && !string.IsNullOrWhiteSpace(B))

return false;

List<string> listA = new List<string>();

for (int i = 0; i < A.Length; i++) {

string strAL = A.Substring(0, i + 1);

string strAR = A.Substring(i + 1, A.Length - i - 1);

//listA.Add(strAL);

//listA.Add(strAR);

listA.Add(strAR + strAL);

}

return listA.FindIndex(r => r == B) >= 0 ? true : false;

}

编辑于 2024-03-31 17:16:48 回复(0)

Java

牛客839384289号

    public boolean solve (String A, String B) {
        // write code here
        int len=A.length();
        for(int i=0;i<len;i++){
            if(A.charAt(i)==B.charAt(0)){
                if((A.substring(i,len)+A.substring(0,i)).equals(B)){
                    return true;
                }
            }
        }
        return false;
    }

编辑于 2024-03-24 14:49:51 回复(0)

占领智商盆地

用最暴力的办法，直接循环截取然后拼接

   // write code here
        if(A.equals(B)){
            return true;
        }
        if (A.length() != B.length()){
            return false;
        }
        String s = A;
        for (int i = 0; i < A.length(); i++) {
           char c = A.charAt(i);
           s = s.substring(1,A.length())+c;
           if (s.equals(B)){
               return true;
           }
        }
        return false;

编辑于 2024-03-04 19:41:13 回复(0)

牛客2024007号

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 旋转字符串
     * @param A string字符串 
     * @param B string字符串 
     * @return bool布尔型
     */
    public boolean solve (String A, String B) {
        // write code here
        // 进阶时间复杂度,还是蛮难的,至少有半个hard难度
        return ((A.length() == B.length()) && (KMPFind(A + A, B)));
    }

    // kmp算法寻找字符串是否在s中
    private boolean KMPFind(String s, String target) {
        int[] next = new int[target.length()];
        getNext(target, next);

        int startS = 0;
        for(int i = 0; i < s.length(); i++) {
            while((startS > 0) && (s.charAt(i) != target.charAt(startS))) {
                startS = next[startS - 1];
            }
            if(s.charAt(i) == target.charAt(startS)) startS++;
            if(startS == target.length()) return true;
        }
        return false;
    }

    private void getNext(String s, int[] next) {
        int endPreFix = 0;
        for(int i = 1; i < next.length; i++) {
            while((endPreFix > 0) && (s.charAt(i) != s.charAt(endPreFix))) {
                endPreFix = next[endPreFix - 1];
            }
            if(s.charAt(i) == s.charAt(endPreFix)) {
                endPreFix++;
            }
            next[i] = endPreFix;
        }
    }
    
}

发表于 2024-01-13 17:24:29 回复(0)

喜欢白菜

找出首字母的下标开始比较，时间复杂度O(n*m）

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 旋转字符串
     * @param A string字符串 
     * @param B string字符串 
     * @return bool布尔型
     */
    bool check(int i,int j,string &A,string &B)
    {
        while(j<B.size())
        {
            if(A[i]!=B[j])
                return false;
            i=(i+1)%A.size();
            ++j;
        }
        return true;
    }
    bool solve(string A, string B) {
        if(A.size()!=B.size())
            return false;
        // write code here
        int i=0;
        int j=0;
        vector<int>r;
        for(int i=0;i<A.size();++i)
        {
            if(A[i]==B[0])
            {
                r.push_back(i);
            }
        }
       for(int i=0;i<r.size();++i)
       {
           if(check(r[i],0,A,B))
           {
               return true;
           }
       }
        return false;
    }
};

发表于 2023-08-16 15:24:50 回复(0)

C++

极至

bool solve(string A, string B) {
        // write code here
        if (A == B)
            return true;
        if (A.length() != B.length())
            return false;
        A += A;
        if (A.find(B) != A.npos)
            return true;
        else
            return false;
    }

发表于 2023-03-10 17:54:49 回复(0)

学习Python的小学生

def if_true(A,B):
    for i in range(0,len(A)):
        a = A[:i+1]
        b = A[i+1:]   
        if ''.join([b,a]) == B: 
            return True

发表于 2023-02-24 23:16:31 回复(0)

小谷围做题家

package main

/**
 * 旋转字符串
 * @param A string字符串 
 * @param B string字符串 
 * @return bool布尔型
*/
func solve( A string ,  B string ) bool {
    if A==B{
        return true
    }
    cnt:=len(A)-1
    for cnt>0{
        A=A[1:]+A[:1]
        if A==B{
            return true
        }
        cnt--
    }
    return false
}

发表于 2023-01-31 22:37:45 回复(0)

Java

coffee_*

简单粗暴(从A的开头取1,2,3.. 加到末尾判断是否和B相等)
import java.util.*;


public class Solution {
    /**
     * 旋转字符串
     * @param A string字符串
     * @param B string字符串
     * @return bool布尔型
     */
    public boolean solve (String A, String B) {
        // write code here
        if (A.equals(B)) {
            return true;
        }
        // boolean flag =false;
        StringBuilder sb = new StringBuilder();

        for (int i = 1; i < A.length(); i++) {

            String temp1 = A.substring(0, i);
            String temp2 = A.substring(i, A.length());

            sb.append(temp2).append(temp1);
            
            if (sb.toString().equals(B)) {
                return true;
            } else {
                sb = new StringBuilder();
            }
        }
        return false;

    }
}

发表于 2022-10-05 19:45:33 回复(0)

Python 3

卡拉什尼科夫

class Solution:
def solve(self , A: str, B: str) -> bool:
# write code here
booll = False
for i in range(len(A)):
s = A[i::] + A[0:i]
if s == B:
booll = True
else:
continue
return booll

发表于 2022-08-28 18:00:31 回复(0)

枉做好人

public boolean solve (String A, String B) {
        if (A.equals(B)) return true;
        int n = A.length();
        for (int i = 0; i <=n ; i++){
            String str = A.substring(i,n)+A.substring(0,i);
            if (str.equals(B)){
            return true;
            }
        }
        return false;

发表于 2022-08-13 23:30:22 回复(0)

Java