2021-08-18：扰乱字符串。使用下面描述的算法可以扰乱字

原创

福大大架构师每日一题

修改于 2021-08-19 10:13:37

2400

修改于 2021-08-19 10:13:37

2021-08-18：扰乱字符串。使用下面描述的算法可以扰乱字符串 s 得到字符串 t ：1.如果字符串的长度为 1 ，算法停止。2.如果字符串的长度 > 1 ，执行下述步骤：在一个随机下标处将字符串分割成两个非空的子字符串。即，如果已知字符串 s ，则可以将其分成两个子字符串 x 和 y ，且满足 s = x + y 。随机决定是要「交换两个子字符串」还是要「保持这两个子字符串的顺序不变」。即，在执行这一步骤之后，s 可能是 s = x + y 或者 s = y + x 。在 x 和 y 这两个子字符串上继续从步骤 1 开始递归执行此算法。给你两个长度相等的字符串 s1 和 s2，判断 s2 是否是 s1 的扰乱字符串。如果是，返回 true ；否则，返回 false 。

福大大答案2021-08-18：

样本对应模型。递归分割字符串 s 和字符串 t 。分割时，s左长度=s右长度，t左长度=t右长度。

代码用golang编写。代码如下：

package main

import "fmt"

func main() {
    s1 := "abcd"
    s2 := "dcba"
    ret := isScramble0(s1, s2)
    fmt.Println(ret)
}

func isScramble0(s1 string, s2 string) bool {
    if (s1 == "" && s2 != "") || (s1 != "" && s2 == "") {
        return false
    }
    if s1 == "" && s2 == "" {
        return true
    }
    if s1 == s2 {
        return true
    }
    if !sameTypeSameNumber(s1, s2) {
        return false
    }
    return process0(s1, 0, len(s1)-1, s2, 0, len(s2)-1)
}

// str1[L1...R1] str2[L2...R2] 是否互为玄变串
// 一定保证这两段是等长的！
func process0(str1 string, L1 int, R1 int, str2 string, L2 int, R2 int) bool {
    if L1 == R1 {
        return str1[L1] == str2[L2]
    }
    for leftEnd := L1; leftEnd < R1; leftEnd++ {
        p1 := process0(str1, L1, leftEnd, str2, L2, L2+leftEnd-L1) && process0(str1, leftEnd+1, R1, str2, L2+leftEnd-L1+1, R2)
        p2 := process0(str1, L1, leftEnd, str2, R2-(leftEnd-L1), R2) && process0(str1, leftEnd+1, R1, str2, L2, R2-(leftEnd-L1)-1)
        if p1 || p2 {
            return true
        }
    }
    return false
}

func sameTypeSameNumber(str1 string, str2 string) bool {
    if len(str1) != len(str2) {
        return false
    }
    map0 := make([]int, 256)
    for i := 0; i < len(str1); i++ {
        map0[str1[i]]++
    }
    for i := 0; i < len(str2); i++ {
        map0[str2[i]]--
        if map0[str2[i]] < 0 {
            return false
        }
    }
    return true
}

执行结果如下：