蠡口87. Scramble String

看到2叉数，想到两组算法：DFS和分治。本题使用分治，答案来自大神basketwang的YouTube解答(https://www.youtube.com/watch?v=Lq3Kr7-qXGI)。希望有一天自己也能独立想出来。

废话不多说，思路是这样: 若S₁和S₂互为scramble string <=> 存在下标idx，使得下图的两种情况之一成立。

为了证明上述命题成立。先定义"a ~ b"表示a与b互为scrabled string，a可以通过一些旋转变成b(通过二叉树的旋转)。

<=, 右推左)：

　　其实等价于(a₁ ~ b₁且a₂ ~ b₂) 或者 (a₁ ~ b₂且a₂ ~ b₁) => a₁+a₂ ~ b₁+b₂ 

　　Case I: 若a₁ ~ b₁且a₂ ~ b₂，那么对于a₁+a₂ -> 把整个字符分成a₁ 和a₂  -> 先将a₁ 变成b₁，再将a₂ 变成b₂ -> 连接a₁和a₂ 变换后的string -> b₁+b₂

　　Case II: 若a₁ ~ b₂且a₂ ~ b₁，那么对于a₁+a₂ -> 把整个字符分成a₁ 和a₂ -> 先将a₁ 变成b₂，再将a₂ 变成b₁ -> 对换a₁和a₂ 变换后的string再连接 -> b₁+b₂

=>，左推右):

　　反证法: 若S₁ ~ S₂, 假设不存在分割idx使得Case I或Case II成立，=> 对于任意idx，Case I和Case II都不成立 => 对于所有idx，（S₁的前idx个字符不能变换得到S2的前idx个字符，或者S₁的后n-idx个字符既不能变换得到S₂的后n-idx个字符）而且（S₁的前idx个字符不能变换得到S₂的后idx个字符，或者S₁的后n-idx个字符既不能变换得到S₂的前n-idx个字符）。说明S₁不能拆分成左右子树，再由左右子树变换之后，连接生成S₂，这与S₁ ~ S₂矛盾。（这个证明好像哪里有点问题，如有错误，欢迎指正）。

这样一来，只要通过分解+递归记得求解，代码如下：

class Solution(object):
    def wordCounts(self,s):
        counts={}
        for c in s: counts[c]=0
        for c in s: counts[c]+=1
        return(counts)
    
    def isScramble(self, s1, s2):
        """
        :type s1: str
        :type s2: str
        :rtype: bool
        """
        if s1==s2: return(True)
        n=len(s1)
        counts1=self.wordCounts(s1)
        counts2=self.wordCounts(s2)
        if counts1!=counts2: return(False)
        for idx in range(1,n):
            s1left,s1right=s1[0:idx],s1[idx:]
            if self.isScramble(s1left,s2[0:idx]) and self.isScramble(s1right,s2[idx:]): return(True)
            if self.isScramble(s1left,s2[(n-idx):]) and self.isScramble(s1right,s2[0:(n-idx)]): return(True)
        return(False)