6.30 - hard - 21

87. Scramble String
这题用递归直接AC了,万万没想到啊,只是加了个sort,开心,下面思考一下用dp的方法, 没想出来,最后看了答案,竟然是三维DP,真是。。。

class Solution(object):
    def isScramble(self, s1, s2):
        """
        :type s1: str
        :type s2: str
        :rtype: bool
        """
        #s1 left is scrambled of s2 left
        #s1 right is scrambled of s2 right
        if sorted(s1) != sorted(s2):
            return False
        if not s1 and not s2:
            return True
        if len(s1) != len(s2):
            return False
        if s1 == s2:
            return True
        res = False
        for i in range(1, len(s1)):
            match11 = self.isScramble(s1[:i], s2[:i])
            match12 = self.isScramble(s1[i:], s2[i:])
            match21 = self.isScramble(s1[:i], s2[-i:])
            match22 = self.isScramble(s1[i:], s2[:-i])
            res = (match11 and match12) or (match21 and match22)
            if res:
                break
        return res
     * Let F(i, j, k) = whether the substring S1[i..i + k - 1] is a scramble of S2[j..j + k - 1] or not
     * Since each of these substrings is a potential node in the tree, we need to check for all possible cuts.
     * Let q be the length of a cut (hence, q < k), then we are in the following situation:
     * 
     * S1 [   x1    |         x2         ]
     *    i         i + q                i + k - 1
     * 
     * here we have two possibilities:
     *      
     * S2 [   y1    |         y2         ]
     *    j         j + q                j + k - 1
     *    
     * or 
     * 
     * S2 [       y1        |     y2     ]
     *    j                 j + k - q    j + k - 1
     * 
     * which in terms of F means:
     * 
     * F(i, j, k) = for some 1 <= q < k we have:
     *  (F(i, j, q) AND F(i + q, j + q, k - q)) OR (F(i, j + k - q, q) AND F(i + q, j, k - q))
     *  
     * Base case is k = 1, where we simply need to check for S1[i] and S2[j] to be equal
class Solution(object):
    def isScramble(self, s1, s2):
        """
        :type s1: str
        :type s2: str
        :rtype: bool
        """
        if len(s1) != len(s2):
            return False
        l = len(s1)
        F = [[[False for _ in range(l+1)] for _ in range(l)] for _ in range(l)]
        for k in range(1, l+1):
            for i in range(l-k+1):
                for j in range(l-k+1):
                    if k == 1:
                        F[i][j][k] = s1[i] == s2[j]
                    else:
                        for q in range(1, k):
                            F[i][j][k] =  F[i][j][k] or (F[i][j][q] and F[i + q][j + q][k - q]) or (F[i][j + k - q][q] and F[i + q][j][k - q])
                            if F[i][j][k]:
                                break
        return F[0][0][l]
        
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 背景 一年多以前我在知乎上答了有关LeetCode的问题, 分享了一些自己做题目的经验。 张土汪:刷leetcod...
    土汪阅读 12,776评论 0 33
  • LeetCode 刷题随手记 - 第一部分 前 256 题(非会员),仅算法题,的吐槽 https://leetc...
    蕾娜漢默阅读 17,941评论 2 36
  • 1. Java基础部分 基础部分的顺序:基本语法,类相关的语法,内部类的语法,继承相关的语法,异常的语法,线程的语...
    子非鱼_t_阅读 31,767评论 18 399
  • Android 自定义View的各种姿势1 Activity的显示之ViewRootImpl详解 Activity...
    passiontim阅读 173,482评论 25 708
  • 版权归作者所有,任何形式转载请联系作者。 作者:不知莫向(来自豆瓣) 来源:https://movie.douba...
    不知莫向阅读 964评论 1 1