87. Scramble String

class Solution(object):
    def isScramble(self, s1, s2):
        """
        :type s1: str
        :type s2: str
        :rtype: bool
        """
        if s1==s2: return True 
        l1=len(s1)
        l2=len(s2)
        d=[[[False for n in xrange(l1+1)]for j in xrange(l2)]for i in xrange(l1)]
        
        for i in xrange(l1):
            for j in xrange(l2):
                if s1[i]==s2[j]:
                    d[i][j][1]=True
        
        for n in xrange(2,l1+1):
            for i in xrange(l1-n+1):
                for j in xrange(l2-n+1):
                    for k in xrange(1,n):
                        if ((d[i][j][k] and d[i+k][j+k][n-k]) or (d[i][j+n-k][k] and d[i+k][j][n-k])):
                            d[i][j][n]=True
        return d[0][0][l1]
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

推荐阅读更多精彩内容