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

题目大意

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