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了