Scramble String(未完待续)

题目链接

题意

见题目链接

解答

因为二叉树是由字符串递归地分割生成的，所以能很自然地想到递归的解法。遍历 s1 的所有可能的分割点，每次分割得到两个非空子字符串 s1_left 和 s1_right，同时对 s2 做同样操作得到 s2_left 和 s2_right，注意到 s2 的左边和右边可能经过“扰乱”操作，所以 s2 有两种分割方式：1. s1_left 与 s2_left 长度相等，2. s1_left 与 s2_right 长度相等。然后判断 s1 和 s2 的子字符串是否能由“扰乱”操作得到。代码实现如下：

递归版本

class Solution:
    def isScramble(self, s1, s2):
        """
        :type s1: str
        :type s2: str
        :rtype: bool
        """
        if len(s1) != len(s2):
            return False
        if len(s1) == 1:
            if s1[0] == s2[0]:
                return True
            else:
                return False
        for l in range(1,len(s1)):
            part11 = s1[:l]
            part12 = s1[l:]
            part21 = s2[:l]
            part22 = s2[l:]
            part31 = s2[-l:]
            part32 = s2[:-l]
            if self.isScramble(part11,part21) and self.isScramble(part12,part22):
                return True
            if self.isScramble(part11,part31) and self.isScramble(part12,part32):
                return True
        return False

但是提交后运行结果是超时:确实，有许多子字符串对被重复求解，类似于递归求斐波那契数列。

斐波那契数列中，我们是用数组保存之前计算得到的结果，这样就能保证每个子问题只被求解一次。那在本题中，能否也将子问题的结果保存起来呢？

[解释部分待完成]

迭代版本

class Solution:
    def isScramble(self, s1, s2):
        """
        :type s1: str
        :type s2: str
        :rtype: bool
        """
        if len(s1) != len(s2):
            return False
        store = [[[False]*(len(s1)+1) for i in range(len(s1))] for j in range(len(s1))]
        for i in range(len(s1)):
            for j in range(len(s1)):
                if s1[i] == s2[j]:
                    store[i][j][1] = True
        
        
        for length in range(1,len(s1)+1):
            for start1 in range(len(s1)-(length-1)):
                for start2 in range(len(s1)-(length-1)):
                    for l in range(1,length):
                        if store[start1][start2][l] and store[start1+l][start2+l][length-l]:
                            store[start1][start2][length] = True
                        if store[start1][start2+length-l][l] and store[start1+l][start2][length-l]:
                            store[start1][start2][length] = True
        return store[0][0][len(s1)]