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
} 複制
執行結果如下：
***
[左神java代碼](https://github.com/algorithmzuo/coding-for-great-offer/blob/main/src/class13/Code03_ScrambleString.java)