[Leetcode][python]Scramble String/扰乱字符串

待我称王封你为后i 2022-05-27 04:15 188阅读 0赞

## 题目大意 ##

[https://leetcode-cn.com/problems/scramble-string/description/][https_leetcode-cn.com_problems_scramble-string_description]  
给出两个等长的字符串 s1 和 s2，判断 s2 是否是 s1 的扰乱字符串。

## 解题思路 ##

### 递归 ###

字符串长度为1：很明显，两个字符串必须完全相同才可以。  
字符串长度为2：当s1=”ab”, s2只有”ab”或者”ba”才可以。  
对于任意长度的字符串，我们可以把字符串s1分为a1,b1两个部分，s2分为a2,b2两个部分，满足（(a1~a2) && (b1~b2)）或者 （(a1~b2) && (a1~b2)）

class Solution(object):
        def isScramble(self, s1, s2):
            """
            :type s1: str
            :type s2: str
            :rtype: bool
            """
            if len(s1)!=len(s2): 
                return False
            if s1==s2: 
                return True
            l1=list(s1)
            l2=list(s2)
            l1.sort()
            l2.sort()
            if l1!=l2: 
                return False
            length=len(s1)
            for i in range(1,length):
                if self.isScramble(s1[:i],s2[:i]) and self.isScramble(s1[i:],s2[i:]): 
                    return True
                if self.isScramble(s1[:i],s2[length-i:]) and self.isScramble(s1[i:],s2[:length-i]): 
                    return True
            return False

### 动态规划 ###

[http://www.blogjava.net/sandy/archive/2013/05/22/399605.html][http_www.blogjava.net_sandy_archive_2013_05_22_399605.html]  
[https://blog.csdn.net/zyz394515661/article/details/78696762][https_blog.csdn.net_zyz394515661_article_details_78696762]  
这里我使用了一个三维数组boolean result\[len\]\[len\]\[len\],其中第一维为子串的长度，第二维为s1的起始索引，第三维为s2的起始索引。  
result\[k\]\[i\]\[j\]表示s1\[i…i+k\]是否可以由s2\[j…j+k\]变化得来。

这题理解很难，如果复习还是直接看看递归吧。

class Solution(object):
        def isScramble(self, s1, s2):
            """
            :type s1: str
            :type s2: str
            :rtype: bool
            """
            if len(s1) != len(s2):
                return False
            dp = [[[0 for _ in range(len(s1))] for _ in range(len(s1))] for _ in range(len(s1))]
            for i in range(len(s1)):
                for j in range(len(s1)):
                    if s1[i] == s2[j]:
                        dp[0][i][j] = 1
    
            for k in range(len(s1)):
                for i in range(len(s1)-k):
                    for j in range(len(s1)-k):
                        if dp[k][i][j] == 0:
                            for q in range(k):
                                if (dp[q][i][j] and dp[k-q-1][i+q+1][j+q+1]) or (dp[q][i][j+k-q] and dp[k-q-1][i+q+1][j]):
                                    dp[k][i][j] = 1
            # print dp
            if dp[-1][0][0] == 1:
                return True
            else:
                return False

[https_leetcode-cn.com_problems_scramble-string_description]: https://leetcode-cn.com/problems/scramble-string/description/
[http_www.blogjava.net_sandy_archive_2013_05_22_399605.html]: http://www.blogjava.net/sandy/archive/2013/05/22/399605.html
[https_blog.csdn.net_zyz394515661_article_details_78696762]: https://blog.csdn.net/zyz394515661/article/details/78696762