87. 擾亂字符串

遞歸：
我們用dg(i,j,length)表示s1[i:i+length]與s2[j:j+length]是否為擾亂字符串。
遞歸的終止條件：
顯然如果s1[i:i+length]與s2[j:j+length]相等，dg(i,j,length)返回True
如果s1[i:i+length]與s2[j:j+length]中的元素不相同，dg(i,j,length)返回False
遞歸過程：
如果s1[i:i+length]與s2[j:j+length]是擾亂字符串，那么就是說，至少存在一個k，k的取值范圍從1到length-1，使得(dg(i+k,j+k,length-k) and dg(i,j,k)) or (dg(i,j+length-k,k) and dg(i+k,j,length-k))為True。
如果我們遍歷所有的k，(dg(i+k,j+k,length-k) and dg(i,j,k)) or (dg(i,j+length-k,k) and dg(i+k,j,length-k))都是False，那么說明s1[i:i+length]與s2[j:j+length]不是擾亂字符串。

代碼：

class Solution:
    def isScramble(self, s1: str, s2: str) -> bool:
        len1 = len(s1)
        if len1!=len(s2):
            return False

        def dg(i,j,length):
            if s1[i:i+length]==s2[j:j+length]:
                return True
            if sorted(s1[i:i+length])!=sorted(s2[j:j+length]):
                return False
            for k in range(1,length):
                if (dg(i+k,j+k,length-k) and dg(i,j,k)) or (dg(i,j+length-k,k) and dg(i+k,j,length-k)):
                    return True
            return False

        return dg(0,0,len1)

關(guān)鍵詞：遞歸