每日一练

美好的一天从“困难”结束！

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/scramble-string/solution/rao-luan-zi-fu-chuan-by-leetcode-solutio-8r9t/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

我自己举了好多例子，才慢慢试出了每部分代码功能。但还是有点迷糊。估计过两天就忘的一干二净了。

个人微改：

import java.util.HashMap;
import java.util.Map;

class scramble{
    int[][][] memo;
    String s1,s2;
    
    public boolean isScramble(String s1,String s2) {
        int length = s1.length();
        this.memo = new int[length][length][length+1];
        this.s1 = s1;
        this.s2 = s2;
        return dfs(0,0,length);
    }
    
    public boolean dfs(int i1,int i2,int length) {
        if(memo[i1][i2][length] != 0) {
            return memo[i1][i2][length] == 1;
        }
        
        if(s1.substring(i1, i1+length).equals(s2.subSequence(i2, i2+length))) {
            memo[i1][i2][length] = 1;
            return true;
        }
        
        if(!checkSimilar(i1, i2, length)) {
            return memo[i1][i2][length] == 1;
        }
        
        for(int i=1;i             //不交换。
            if(dfs(i1,i2,i)&&dfs(i1+i,i2+i,length-i)) {
                memo[i1][i2][length] = 1;
                return true;
            }
            if(dfs(i1,i2+length-i,i)&&dfs(i1+i,i2,length-i)) {
                memo[i1][i2][length] = 1;
                return true;
            }
        }
        memo[i1][i2][length] = -1;
        return false;
    }
    
    public boolean checkSimilar(int i1,int i2,int length) {
        Map freq = new HashMap();
        for(int i = i1;i< i1+length;i++) {
            char c = s1.charAt(i);
            freq.put(c, freq.getOrDefault(c, 0)+1);
        }
        for(int i = i2;i< i2+length;i++) {
            char c = s2.charAt(i);
            freq.put(c, freq.getOrDefault(c, 0)-1);
        }
        for(Map.Entry entry:freq.entrySet()) {
            int value = entry.getValue();
            if(value != 0) {
                return false;
            }
        }
        return true;
    }
}

public class ScarmbleString {
    public static void main(String args[]) {
        String str1 = "great";
        String str2 = "rgeat";
        scramble hah = new scramble();
        System.out.println(hah.isScramble(str1, str2));
    }
}