leetcode题解87：扰乱字符串

描述

该题来自于力扣第87题

分析

没什么好的办法，直接递归暴力，遍历切割点，然后判断字符串的两边是否互为扰乱字符串就好。比如great和rgeat，如果切割点在g reat，那么递归查看g与r，reat与geat是否互为扰乱字符串？还有一种就是翻转了，即递归查看g与t，reat与rgea是否互为扰乱字符串？两种情况一种满足则返回True。都不满足则继续遍历下一个切割点gr eat。

注意到两个字符串互为扰乱串，长度比如相同，所以可以使用三个入参的函数bool func(i1,i2,length)表示字符串s1[i1:i1+length]与字符串s2[i2:i2+length]是否互为扰乱串，然后递归调用func就好。

该题如果直接递归的话会超时，需要一些小技巧，注意到在递归过程中，可能会涉及到重复计算，会重复判断两个字符串是否是扰乱字符串，所以可以将计算后的结果存储下来，最简单的方法使用一个多维数组记录递归的结果，对于python，可以使用functools.cache装饰器来缓存已经计算好的结果。

代码

class Solution:
    def isScramble(self, s1: str, s2: str) -> bool:
        @cache
        def dfs(i1, i2, length):
            if s1[i1:i1+length] == s2[i2:i2+length]:
                return True
            if sorted(s1[i1:i1+length]) != sorted(s2[i2:i2+length]):
                return False
            for i in range(1, length):
                if dfs(i1, i2, i) and dfs(i1+i, i2+i, length-i):
                    return True
                if dfs(i1, i2+length-i, i) and dfs(i1+i, i2, length-i):
                    return True
            return False

        ans = dfs(0, 0, len(s1))
        dfs.cache_clear()
        return ans