2021-02-12：如何判断两个字符串是否互为旋转字符串？

福哥答案2021-02-12：

假设字符串str1是“ABCDE”，字符串str2是“CDEAB”。字符串str2可以拆分成“CDE”和“AB”，可以拼成“ABCDE”。所以str1和str2互为旋转字符串。

解法：
1.判断str1和str2的字符串长度是否相等。不等返回false；相等进行下一步。
2.设str=str1+str1，判断str是否包含str2。如果包含，是旋转字符串。如果不包含，说明不是旋转字符串。
字符串是否包含子字符串，可以用相应语言的系统自带函数，也可以用kmp算法。

代码用golang编写，代码如下：

package mainimport ("fmt""strings"
)func main() {str1 := "ABCDE"str2 := "CDEAB"ret := rotateString1(str1, str2)fmt.Println("1.系统自带函数：", ret)ret = rotateString2(str1, str2)fmt.Println("2.kmp算法：", ret)
}//1.系统自带函数
func rotateString1(A string, B string) bool {return len(A) == len(B) && strings.Contains(A+A, B)
}//2.kmp算法
func rotateString2(A string, B string) bool {return len(A) == len(B) && kmp(A+A, B) >= 0
}func kmp(s string, m string) int {sLen := len(s)mLen := len(m)if sLen < mLen {return -1}if mLen == 0 {return 0}next := getNextArray(m)x := 0y := 0for x < sLen && y < mLen {if s[x] == m[y] {x++y++} else if y > 0 {y = next[y]} else {x++}}if y == mLen {return x - y} else {return -1}
}func getNextArray(m string) []int {mLen := len(m)if mLen == 1 {return []int{-1}}next := make([]int, mLen)next[0] = -1cn := 0for i := 2; i < mLen; i++ {if m[i-1] == m[cn] {cn++next[i] = cni++} else if cn > 0 {cn = next[cn]} else {i++}}return next
}

执行结果如下：

---

力扣796.旋转字符串
评论