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

福大大架构师每日一题 · · 466 次点击 · · 开始浏览

这是一个创建于的文章，其中的信息可能已经有所发展或是发生改变。

福哥答案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
}

执行结果如下：