2021-02-12:如何判断两个字符串是否互为旋转字符串?
【摘要】 2021-02-12:如何判断两个字符串是否互为旋转字符串?福哥答案2021-02-12:假设字符串str1是“ABCDE”,字符串str2是“CDEAB”。字符串str2可以拆分成“CDE”和“AB”,可以拼成“ABCDE”。所以str1和str2互为旋转字符串。解法:1.判断str1和str2的字符串长度是否相等。不等返回false;相等进行下一步。2.设str=str1+str1,判断...
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编写,代码如下:
```go
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://leetcode-cn.com/problems/rotate-string/)
[评论](https://user.qzone.qq.com/3182319461/blog/1613086311)
【声明】本内容来自华为云开发者社区博主,不代表华为云及华为云开发者社区的观点和立场。转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息,否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱:
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
作者其他文章
- 2025-08-14:奇偶频次间的最大差值Ⅱ。用go语言,给你一个字符串 s 和一个整数 k。请从 s 中选取任意一个长度不少于
- 2025-08-13:使数组包含目标值倍数的最少增量。用go语言,给出两个整数数组 nums 和 target。每一步可以把 n
- 2025-08-12:K次修改后的最大曼哈顿距离。用go语言,给出一个只包含字符 ‘N‘、‘S‘、‘E‘、‘W‘ 的字符串 s,
- 2025-08-11:奇偶频次间的最大差值Ⅰ。用go语言,给定一个只含小写字母的字符串 s。对任意两个字符 x 和 y(它们在
- 2025-08-10:变成好标题的最少代价。用go语言,给你一个长度为 n 的字符串 caption。我们把“好标题”定义为:字
评论(0)