ac

一个字符串可以分解为多种二叉树。如果str长度为1，认为不可分解；如果str长度为N(N>1),左半部分长度可以为1~N-1，右半部分为剩下的长度，然后你可以交换左右两部分。并且左右部分可以按照同样的逻辑，继续分解。每一个形成的字符串都可以是原字符串的旋变字符串。现在给你两个字符串str1和str2，判断str2是否为str1的旋变字符串。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static Scanner sc = new Scanner(System.in);

    public static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws Exception {
        String str1 = reader.readLine();
        String str2 = reader.readLine();
        System.out.println(isChange(str1, str2) ? "YES" : "NO");
    }

    static boolean isChange(String s1, String s2){
        if ((s1 == null && s2 != null) || (s1 != null && s2 == null)) {
            return false;
        }
        if ((s1 == null && s2 == null) || (s1.equals(s2))) {
            return true;
        }
        if(s1.length() != s2.length()){
            return false;
        }
        char[] arr1 = s1.toCharArray();
        char[] arr2 = s2.toCharArray();
        int n = arr1.length;
        // dp[L1][L2][size] 表示str1以L1位置开始长度为size的字符子串 与 str2以L2位置开始长度为size的字符子串是否互为旋变字符串
        boolean[][][] dp = new boolean[n][n][n + 1];

        // 长度为1判断是否相等
        for(int l1=0;l1<n;l1++){
            for(int l2=0;l2<n;l2++){
                dp[l1][l2][1] = arr1[l1] == arr2[l2];
            }
        }

        // size=2, 一直到size = n
        for(int size=2;size<=n;size++){
            for(int l1=0;l1<=n-size;l1++){
                for(int l2=0;l2<=n-size;l2++){
                    // 依据size分成左右两部分
                    for(int left=1;left<size;left++){
                        // 左右两部分
                        if(dp[l1][l2][left] && dp[l1+left][l2+left][size-left]){
                            dp[l1][l2][size] = true;
                            break;
                        }
                        // 可以旋转下
                        if(dp[l1][l2+size-left][left] && dp[l1+left][l2][size-left]){
                            dp[l1][l2][size] = true;
                            break;
                        }
                    }
                }
            }
        }
        return dp[0][0][n];
    }

}
/*

 */