首页 > 试题广场 >

旋转字符串

[编程题]旋转字符串
  • 热度指数:13617 时间限制: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字符串长度满足 ,保证字符串中仅包含小写英文字母和阿拉伯数字
进阶: 时间复杂度 ,空间复杂度
示例1

输入

"youzan","zanyou"

输出

true
示例2

输入

"youzan","zyouan"

输出

false
示例3

输入

"nowcoder","nowcoder"

输出

true
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)
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 回复(2)
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)
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)
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)
看其他人的思路:
每次从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)
用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)
8岁李琛解法:
 public boolean solve (String A, String B) {
        // write code here

        if (A.equals(B)) return true;
        if (A.length() != B.length()) return false;

        if (A.length() > 0) {
            for (int i = 1; i < A.length(); i++)
                if ((A.substring(i) + A.substring(0, i)).equals(B))return true;
        }

        return false;
    }


发表于 2024-06-27 11:39:27 回复(0)
字符串A后面再加个字符串A,然后找子串是否有B
bool solve(string A, string B)
    {
        if(A.size() != B.size()) return false;
        return (A + A).find(B) != -1;
    }


发表于 2024-05-29 21:56:41 回复(0)
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)
    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)
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)
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)
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)
简单粗暴(从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)
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)