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]
