蛮三刀酱的博客

技术公众号:后端技术漫谈

【Leetcode】【python】Scramble String 扰乱字符串

发表于 更新于 分类于 阅读次数： Valine：

题目大意

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两个部分，满足（(a1a2) && (b1b2)）或者 （(a1b2) && (a1b2)）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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
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]变化得来。

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
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