Scramble String：三維動態規劃判斷擾亂字符串

問題定義

給定等長字符串 s1, s2，判斷 s2 是否為 s1 的「擾亂字符串」。擾亂定義：將字符串遞歸二分構成二叉樹，任選非葉節點交換左右子樹，產生的字符串即為擾亂字符串。

三維 DP 狀態

• scrambled[i][j][len]：s1 從 i 開始、s2 從 j 開始、長度為 len 的子串是否互為擾亂關係
• i ∈ [0, n-1], j ∈ [0, n-1], len ∈ [1, n]

轉移方程

長度 len ≥ 2 時，枚舉分割點 k (1 ≤ k < len)：

• 不交換：左對左、右對右 → scrambled[i][j][k] && scrambled[i+k][j+k][len-k]
• 交換：左對右、右對左 → scrambled[i][j+len-k][k] && scrambled[i+k][j][len-k]
• 任一成立則 scrambled[i][j][len] = true

填表順序

• len 從 2 到 n 遞增（依賴較短長度）
• i, j 從大到小遞減（或任意，只要子問題已算）
• 基例：len=1 時比較字符是否相等；len=0 設 true

Java 實現

public boolean isScramble(String s1, String s2) {
    if (s1.equals(s2)) return true;
    int n = s1.length();
    boolean[][][] dp = new boolean[n][n][n+1];
    for(int i=0;i=0;i--) for(int j=n-1;j>=0;j--)
        for(int len=2; len<=Math.min(n-i,n-j); len++)
            for(int k=1; k

複雜度與優化

時間 O(n⁴)（四重循環），空間 O(n³)。n ≤ 30 時可接受（LeetCode 原題限制）
剪枝：若字符頻率不同直接 false；DP 中提前 break
更優解法：遞歸 + 記憶化 + 字符頻率剪枝，實際運行更快


核心洞察
擾亂關係保持字符多集合不變，且遞歸結構對應二叉樹分割。三維 DP 窮舉所有分割與交換組合，是區間 DP 的經典應用。