力扣第87题-扰乱字符串

力扣链接:87. 扰乱字符串 - 力扣（LeetCode）

思路:
从一个位置将两个字符串分别划分成两个子串，然后递归判断两个字符串的两个子串是否互相为扰乱字符串。因为不知道在哪个位置分割字符串，所以直接遍历每个位置进行分割。在判断是否两个子串能否通过翻转变成相等的时候，需要保证传给函数的子串长度是相同的。
我们分两种情况讨论:互换和不互换
终止条件就是,当长度是1的两个字符串是否相等
记忆化递归用到python的缓存库,将已经计算过的结果保存到缓存中,再计算时在缓存中,不用再次计算

import functools
@functools.lru_cache(None)

import functools@functools.lru_cache(None)
def isScramble(s1: str, s2: str):N = len(s1)if N == 0:return Trueif N == 1:return s1 == s2     # 最终的递归出口if sorted(s1) != sorted(s2):return Falsefor i in range(1, N):if isScramble(s1[:i], s2[:i]) and isScramble(s1[i:], s2[i:]):return Trueelif isScramble(s1[:i], s2[-i:]) and isScramble(s1[i:], s2[:-i]):return Truereturn Falseprint(isScramble("great", "rgeat"))