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

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
}