87. Disturb string

---

Preface

Using the algorithm described below, you can scramble strings s Get a string t ：
If the length of the string is 1 , Algorithm stop
If the length of the string > 1 , Perform the following steps ：
Splits a string into two non empty substrings at a random subscript . namely , If you know the string s , You can split it into two substrings x and y , And meet s = x + y .
Random The decision is to 「 Swap two substrings 」 Still 「 Keep the order of the two substrings unchanged 」. namely , After performing this step ,s May be s = x + y perhaps s = y + x .
stay x and y These two substrings continue from step 1 Start recursive execution of this algorithm .
Here are two for you Equal length String s1 and s2, Judge s2 Whether it is s1 The scrambled string . If it is , return true ; otherwise , return false .

source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/scramble-string

Recurrence of violence

Sample correspondence model
According to the situation of the first knife

Defined function f(s1,L1,R1, s2,L2,R2):
str1 Of L1-R1, Yes str2 L2-R2 Equal length , see str1 Of L1~R1, Yes str2 L2~R2 Is this a mysterious string

base case
When you L1 To R1 There is only one character on ,
If str1[L1]==str2[L2], return true

General situation
The enumeration method is str1 Where is the first cut
1) The first shot 0-0, 1-9

Two cases
1. The two strings correspond one by one
2.str1 The first part is for str2 Rear part ,str1 Corresponding to the latter part str2 The first part
That is, the characters are transformed

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]  Are they mysterious strings 
	//  Make sure these two paragraphs are of equal length ！
	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;
	}

Two 、 Memory search

If we use a four-dimensional table to record , That would be a waste of space
We can reduce one dimension , Use 3D table
The recursive parameter is set to

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

use size Can be launched R1 and R2
This saves space

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;
    }
}