13

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

 4 years ago
source link: https://studygolang.com/articles/33318
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

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

福大大架构师每日一题 · 1天之前 · 70 次点击 · 预计阅读时间 1 分钟 · 不到1分钟之前 开始浏览    

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
}

执行结果如下：

b1fb7e889f7244396e153326c9c1754a.png
在这里插入图片描述

力扣796.旋转字符串
评论

有疑问加站长微信联系（非本文作者）

280

report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK