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 main
import (
"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 := 0
y := 0
for 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] = -1
cn := 0
for i := 2; i < mLen; i++ {
if m[i-1] == m[cn] {
cn++
next[i] = cn
i++
} else if cn > 0 {
cn = next[cn]
} else {
i++
}
}
return next
}
執行結果如下：
力扣796.旋轉字串
評論
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/259230.html
標籤：其他
上一篇：高精度加法