LeetCode Scramble String：字符串擾亂判斷的遞歸與剪枝策略

LeetCode Scramble String：字符串擾亂判斷的遞歸與剪枝策略

給定兩個等長字符串 s1, s2，判斷 s2 是否為 s1 的「擾亂字符串」。擾亂操作定義為：將字符串遞歸二分，任意非葉節點交換左右子樹。

問題本質

擾亂相當於在二叉樹分割表示中交換子樹。判斷 s2 是否可由 s1 經過若干次交換得到，等價於：存在某個分割點 k (1 ≤ k < n)，使得以下兩種情況之一成立：

1. 不交換：s1[0..k-1] 與 s2[0..k-1] 互為擾亂，且 s1[k..n-1] 與 s2[k..n-1] 互為擾亂。
2. 交換：s1[0..k-1] 與 s2[n-k..n-1] 互為擾亂，且 s1[k..n-1] 與 s2[0..n-k-1] 互為擾亂。

遞歸解法與剪枝

• 基礎情況：s1 == s2 返回 true；字符頻率不同 (排序後不等) 直接返回 false。
• 窮舉分割點 k 從 1 到 n-1，遞歸檢查上述兩種情況，任一成立即返回 true。
• 備忘錄優化：使用 map<pair<string,string>, bool> 記錄已計算結果，避免重複計算，將指數複雜度降至多項式。

Python 實現 (含備忘錄)

class Solution:
    def __init__(self):
        self.memo = {}
    
    def isScramble(self, s1: str, s2: str) -> bool:
        if (s1, s2) in self.memo:
            return self.memo[(s1, s2)]
        if s1 == s2:
            self.memo[(s1, s2)] = True
            return True
        if sorted(s1) != sorted(s2):  # 剪枝：字符集不同
            self.memo[(s1, s2)] = False
            return False
        
        n = len(s1)
        for i in range(1, n):
            # 情況一：不交換
            if self.isScramble(s1[:i], s2[:i]) and self.isScramble(s1[i:], s2[i:]):
                self.memo[(s1, s2)] = True
                return True
            # 情況二：交換
            if self.isScramble(s1[:i], s2[n-i:]) and self.isScramble(s1[i:], s2[:n-i]):
                self.memo[(s1, s2)] = True
                return True
        self.memo[(s1, s2)] = False
        return False

複雜度分析

無備忘錄時為指數級。加入備忘錄後，狀態數為 O(n^4) (所有子串對)，每狀態 O(n) 窮舉分割點，總時間 O(n^5)，空間 O(n^4)。實際運行極快。