87. Scramble String
检查字串 s1 是否能用以下方法转移到字串 s2:
1.如果字串长度是1 -> 停止
2.如果大于1 -> 将字串切成两段，可以交换两段的顺序，也可以不交换
接着递回操作这两段字串
Example 1:
Input: s1 = "great", s2 = "rgeat"
Output: true
great -> gre / at -> 不交换
gre -> gr/e -> 不交换
gr -> g/r -> 交换成 r/g
所以最后会变成 r/g / e / at
Example 2:
Input: s1 = "abcde", s2 = "caebd"
Output: false
Example 3:
Input: s1 = "a", s2 = "a"
Output: true
思路:
1.模拟转移的过程递回检查，枚举字串的切割点 index i，
如果不交换顺序-> 递回检查 s1[0 ~ i] 能否转移到 s2[0 ~ i]
以及 s1[i ~ len(s1)] 能否转移到 s2[i ~ len(s2)]
如果交换顺序 -> 递回检查 s1[0 ~ i] 能否转移到 s2[len(s2)-i ~ len(s2)]
以及 s1[i ~ len(s1)] 能否转移到 s2[0 ~ len(s2)-i]
2.因此可以写出以下 dp 式子:
dp[s1开始, s1结束, s2开始, s2结束] = True
if any( (dp[s1开始, i, s2开始, i] and dp[i, s1结束, i, s2结束]) #不交换的情况
or (dp[s1开始, i, s2结束-(i-s1开始), s2结束] and
dp[i, s1结束, s2开始, s2结束-(i-s1开始))] #交换的情况
for i in range(s1开始, s1结束))
总之就是用两段字串在原s1 s2中的位置去当 dp 的 index
3.因为两段字串长度要相等，所以可以用 [s1开始, s2开始, 字串长度] 当 index就好
变成是切成 dp[s1开始, s2开始, i] and dp[s1开始+i, s2开始+i, 字串长度-i] #不交换
和 dp[s1开始, s2开始+字串长度-i, i] and dp[s1开始+i, s2开始, 字串长度-i] #交换
4.可以比对两个字串的Counter是否相等来剪枝
直接比较 sort 后的结果是否相同即可
Python code:
class Solution:
def isScramble(self, s1: str, s2: str) -> bool:
@cache
def dp(i1, i2, length):
if length == 1:
return s1[i1] == s2[i2]
if sorted(s1[i1:i1+length]) != sorted(s2[i2:i2+length]):
return False
for i in range(1, length):
if (dp(i1, i2, i) and dp(i1+i, i2+i, length-i)) or (dp(i1,
i2+length-i, i) and dp(i1+i, i2, length-i)):
return True
return False
return dp(0, 0, len(s1))
好久没PO了