這道題中文版翻譯的已經有一部分提示了，還把樹的結構給畫了出來。英文版新版只給了兩個轉換規則
We can scramble a string s to get a string t using the following algorithm:
If the length of the string is 1, stop.If the length of the string is > 1, do the following:Split the string into two non-empty substrings at a random index, i.e., if the string is s, divide it to x and y where s = x + y.Randomly decide to swap the two substrings or to keep them in the same order. i.e., after this step, s may become s = x + y or s = y + x.Apply step 1 recursively on each of the two substrings x and y.Given two strings s1 and s2 of the same length, return true if s2 is a scrambled string of s1, otherwise, return false.87. 擾亂字符串給定一個字符串 s1，我們可以把它遞歸地分割成兩個非空子字符串，從而將其表示為二叉樹。
下圖是字符串 s1 = "great" 的一種可能的表示形式。
great / \ gr eat / \ / \g r e at / \ a t在擾亂這個字符串的過程中，我們可以挑選任何一個非葉節點，然後交換它的兩個子節點。
例如，如果我們挑選非葉節點 "gr" ，交換它的兩個子節點，將會產生擾亂字符串 "rgeat" 。
rgeat / \ rg eat / \ / \r g e at / \ a t我們將 "rgeat」 稱作 "great" 的一個擾亂字符串。
同樣地，如果我們繼續交換節點 "eat" 和 "at" 的子節點，將會產生另一個新的擾亂字符串 "rgtae" 。
rgtae / \ rg tae / \ / \r g ta e / \ t a我們將 "rgtae」 稱作 "great" 的一個擾亂字符串。
給出兩個長度相等的字符串 s1 和 s2，判斷 s2 是否是 s1 的擾亂字符串。
示例 1:
輸入: s1 = "great", s2 = "rgeat"輸出: true示例 2:
輸入: s1 = "abcde", s2 = "caebd"輸出: false來源：力扣（LeetCode）
連結：https://leetcode-cn.com/problems/scramble-string
Link：https://leetcode.com/problems/scramble-string/
暴力破解O(5^N)
如果切割，使得原字符串與目標字符串分別左右相等或者交叉相等, 就說明能夠轉換成功
這裡需要保證，每次遞歸調用函數，兩個入參長度相等，len(s1) == len(s2)
# 分割不交換left right
｜ ｜
left right
# 分割交換left | right \ / X / \left | right代碼實現class Solution: def isScramble(self, s1: str, s2: str) -> bool: if s1 == s2: return True
length = len(s1) for k in range(1, length): if self.isScramble(s1[0 : k], s2[0 : k]) and self.isScramble(s1[k : length], s2[k : length]): return True
if self.isScramble(s1[0 : k], s2[length - k : length]) and self.isScramble(s1[k : length], s2[0 : length - k]): return True時間複雜度# for循環中判斷時間 = T(K) + T(N - K), 一共有兩個判斷x2T(N) = for k in 1...n-1: 2 * (T(k) + T(N - k))
= 2(T(1) + T(N - 1) + T(2) + T(N - 2) + ... + T(N - 1) + T(1))
= 2 * 2(T(1) + T(2) + ... + T(N - 1))
= 4(T(1) + T(2) + ... + T(N - 1))
# 同理, 替換下面左邊部分T(N - 1) = 4(T(1) + T(2) + ... + T(N - 2))
= 4(T(1) + T(2) + ... + T(N - 2)) + 4T(N - 1)
= T(N - 1) + 4T(N - 1)
= 5T(N - 1)
# 所以T(N) = 5 * T(N - 1) = 5^2 * T(N - 2) = 5 ^ N * T(1) = 5^N遞歸 + 記憶化搜索 + 剪枝剪枝: 只是在暴力搜索的過程中，如果能夠提前判斷結果，比如"aab", "aac"裡面字符個數不相等, 就不用再判斷了
記憶化搜索: 是指可能出現重複的調用過程，使用緩存來記錄(入參1, 入參2) -> (結果), 就不用再計算一遍了
理論上: 搜索 + 記憶化搜索 = 動態規劃
⚠️剪枝能夠提高搜索效率，但是理論的時間複雜度並沒有減少，可以假設一個Case，每次判斷都能通過剪枝攔截
from functools import lru_cachefrom collections import Counterclass Solution: @lru_cache(maxsize=None) # 記憶化搜索 def isScramble(self, s1: str, s2: str) -> bool: if s1 == s2: return True
if Counter(s1) != Counter(s2): return False
length = len(s1) for k in range(1, length): if self.isScramble(s1[0 : k], s2[0 : k]) and self.isScramble(s1[k : length], s2[k : length]): return True
if self.isScramble(s1[0 : k], s2[length - k : length]) and self.isScramble(s1[k : length], s2[0 : length - k]): return True動態規劃狀態定義dp[i][j][k], 定義同長度的s1[i : i + k], s2[j : j + k]是否可以成功轉換
狀態轉換# 左右分別可轉換s1 [ left1 | right1 ] i i + cut i + k -1
| |
s2 [ left2 | right2 ] j j + cut j + k - 1
dp[i][j][k] = (dp[i][j][cut] and dp[i + cut][j + cut][k - cut])
# 左右交叉可轉換s1 [ left1 | right1 ] i i + cut i + k -1
\ / X / \
s2 [ left2 | right2 ] j j + k - cut j + k - 1
dp[i][j][k] = (dp[i][j + k - cut][cut] and dp[i + cut][j][k - cut])計算方向字符串k = 1到N
邊界條件長度k從1開始，所以開數組的時候要多一位
當k = 1時，只要判斷單個字符串是否相等即可
class Solution: def isScramble(self, s1: str, s2: str) -> bool: if len(s1) != len(s2): return False
length = len(s1) dp = [[[False for _ in range(length + 1)] for _ in range(length)] for _ in range(length)]
for i in range(length): for j in range(length): dp[i][j][1] = (s1[i] == s2[j])
for k in range(2, length + 1): for i in range(length - k + 1): for j in range(length - k + 1): for cut in range(1, k - 1 + 1):
if (dp[i][j][cut] and dp[i + cut][j + cut][k - cut]): dp[i][j][k] = True break
if (dp[i][j + k - cut][cut] and dp[i + cut][j][k - cut]): dp[i][j][k] = True break
return dp[0][0][length]--End--