室内设计学校广州/附子seo教程

旋转字符串

任意给定两个字符串，返回这两个字符串是否互为旋转字符串

旋转字符串定义

题解

第一步：先判断两个字符串长度是否一样，如果不一样直接返回false。

如果第一步过了，然后生成 str1+str1 的一个大字符串，称为 str1’

然后判断 str2 是不是 str1’ 的一个子串即可

为啥呢？是不是觉得应该有很多反例？

其实，拼接后的大字符串中，任何跟 str2 长度相等的子串都是原始串的旋转串

代码

package com.harrison.class16;/*** @author Harrison* @create 2022-03-30-14:04* @motto 众里寻他千百度，蓦然回首，那人却在灯火阑珊处。*/
public class Code02_IsRotation {public static boolean isRotation(String a,String b){if(a==null || b==null || a.length()!=b.length()){return false;}String b2=b+b;return getIndexOf(b2,a)!=-1;}public static int getIndexOf(String s1,String s2){if(s1.length()<s2.length()){return -1;}char[] str1=s1.toCharArray();char[] str2=s2.toCharArray();int[] next=getNextArray(str2);int x=0;int y=0;while(x<s1.length() && y<s2.length()){if(str1[x]==str2[y]){x++;y++;}else if(next[y]==-1){x++;}else{y=next[y];}}return y==s2.length()?x-y:-1;}public static int[] getNextArray(char[] str2){if(str2.length==1){return new int[]{-1};}int[] next=new int[str2.length];next[0]=-1;next[1]=0;int i=2;int cn=0;while(i<next.length){if(str2[i-1]==str2[cn]){next[i++]=cn;}else if(cn>0){cn=next[cn];}else{next[i++]=0;}}return next;}public static void main(String[] args) {String str1 = "liaohongsi";String str2 = "hongsiliao";System.out.println(isRotation(str1, str2));}
}