87. 扰乱字符串

---

前言

使用下面描述的算法可以扰乱字符串 s 得到字符串 t ：
如果字符串的长度为 1 ，算法停止
如果字符串的长度 > 1 ，执行下述步骤：
在一个随机下标处将字符串分割成两个非空的子字符串。即，如果已知字符串 s ，则可以将其分成两个子字符串 x 和 y ，且满足 s = x + y 。
随机 决定是要「交换两个子字符串」还是要「保持这两个子字符串的顺序不变」。即，在执行这一步骤之后，s 可能是 s = x + y 或者 s = y + x 。
在 x 和 y 这两个子字符串上继续从步骤 1 开始递归执行此算法。
给你两个 长度相等 的字符串 s1 和 s2，判断 s2 是否是 s1 的扰乱字符串。如果是，返回 true ；否则，返回 false 。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/scramble-string

暴力递归

样本对应模型
按第一刀的情况来分

定义函数f(s1,L1,R1, s2,L2,R2):
str1的L1-R1,对str2 L2-R2等长，看str1的L1~R1,对str2 L2~R2这一段是不是玄变字符串

base case
当你L1到R1上只有一个字符，
如果str1[L1]==str2[L2],返回true

普遍情况
枚举的方式是str1第一刀切哪儿了
1)第一刀0-0, 1-9

两种情况
1.两个字符串一一对应
2.str1前部分对于str2后部分,str1后部分对应str2前部分
即字符进行了变换

2)0-1,2-9
…
9)0-8,9-9

	public static boolean isScramble(String s1, String s2) {
    
		if ((s1 == null && s2 != null) || (s1 != null && s2 == null)) {
    
			return false;
		}
		if (s1 == null && s2 == null) {
    
			return true;
		}
		if (s1.equals(s2)) {
    
			return true;
		}
		char[] str1 = s1.toCharArray();
		char[] str2 = s2.toCharArray();
		if (!sameTypeSameNumber(str1, str2)) {
    
			return false;
		}
		return process0(str1, 0, str1.length - 1, str2, 0, str2.length - 1);
	}

	// str1[L1...R1] str2[L2...R2] 是否互为玄变串
	// 一定保证这两段是等长的！
	public static boolean process(char[] str1, int L1, int R1, char[] str2, int L2, int R2) {
    
		if (L1 == R1) {
    
			return str1[L1] == str2[L2];
		}
		for (int leftEnd = L1; leftEnd < R1; leftEnd++) {
    
			boolean p1 = process0(str1, L1, leftEnd, str2, L2, L2 + leftEnd - L1)
					&& process0(str1, leftEnd + 1, R1, str2, L2 + leftEnd - L1 + 1, R2);
			boolean p2 = process0(str1, L1, leftEnd, str2, R2 - (leftEnd - L1), R2)
					&& process0(str1, leftEnd + 1, R1, str2, L2, R2 - (leftEnd - L1) - 1);
			if (p1 || p2) {
    
				return true;
			}
		}
		return false;
	}

二、记忆化搜索

如果我们使用四维表记录的话,那就太浪费空间了
我们可以减少一维,使用三维表
递归参数设置为

process(char[] str1,int L1,char[] str2,int L2,int size,int[][][] dp)

用size可以推出R1和R2
这样就可以节省空间了

class Solution {
    
    public boolean isScramble(String s1, String s2) {
    
        if ((s1 == null && s2 != null) || (s1 != null && s2 == null)) {
    
			return false;
		}
		if (s1 == null && s2 == null) {
    
			return true;
		}
		if (s1.equals(s2)) {
    
			return true;
		}
        char[] str1=s1.toCharArray();
        char[] str2=s2.toCharArray();
        int size=str1.length;
        int[][][] dp=new int[size][size][size+1];
        return process(str1,0,str2,0,size,dp);
    }
    
    public boolean process(char[] str1,int L1,char[] str2,int L2,int size,int[][][] dp){
    
        if(dp[L1][L2][size]!=0){
    
            return dp[L1][L2][size]==1;
        }
        boolean ans = false;
        if(size==1){
    
           ans=str1[L1]==str2[L2];
        }else{
    
            for(int leftPart=1;leftPart<size;leftPart++){
    
                boolean p1=process(str1,L1,str2,L2,leftPart,dp)
                &&process(str1,L1+leftPart,str2,L2+leftPart,size-leftPart,dp);
                boolean p2=process(str1,L1,str2,L2+size-leftPart,leftPart,dp)&&
                process(str1,L1+leftPart,str2,L2,size-leftPart,dp);
                if(p1||p2){
    
                    ans=true;
                    break;
                }
            }
        }
        dp[L1][L2][size]=ans?1:-1;
        return ans;
    }
}