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-03-06:给定一个长度为 n 的整数组 nums,其中 n 是偶数,同时还有一个整数 k。 你可以进行一些操作,每次
- 绝了!k3s (k8s) 安装 ollama 运行 deepseek 全流程揭秘,yaml全公开
- 2025-03-04:求出硬币游戏的赢家。用go语言,给定两个正整数 x 和 y,分别代表75元和10元硬币的数量。 Alice
- 2025-03-03:切蛋糕的最小总开销Ⅱ。用go语言,你有一个大小为 m x n 的矩形蛋糕,需要将其切割成 1 x 1 的小
- 2025-03-02:切蛋糕的最小总开销Ⅰ。用go语言,有一个大小为 m x n 的矩形蛋糕,我们需要将其切成 1 x 1 的小
评论(0)