🌕🌕 87. 扰乱字符串

难度: 🌕🌕

问题描述

---

解法

class Solution {
    public boolean isScramble(String s1, String s2) {
        // 思路：
        // dp[i][j][k] - 以 [i] 为左边界，[j] 为左边界，len == k 的字符串是否为扰乱字符串
        int len = s1.length();
        if(len == 1) {
            return s1.equals(s2);
        }
        if(s1.equals(s2)) {
            return true;
        }
        // len > 1
        boolean[][][] dp = new boolean[len][len][len + 1];
        // 初始化
        for(int i = 0; i < len; i ++) {
            for(int j = 0; j < len; j ++) {
                if(s1.charAt(i) == s2.charAt(j)) {
                    dp[i][j][1] = true;
                }
            }
        }
        // dp
        for(int size = 2; size <= len; size ++) {
            for(int i = 0; i < len - size + 1; i ++) {
                for(int j = 0; j < len - size + 1; j ++) {
                    for(int k = 1; k < size; k ++) {
                        // System.out.println(i + "  " + j  + "  " + k);
                        if((dp[i][j][k] && dp[i + k][j + k][size - k]) 
                            || (dp[i][j + size - k][k] && dp[i + k][j][size - k])) {
                            dp[i][j][size] = true;
                            // System.out.println(i + "  " + j  + "  " + k + " --------");
                        }
                    }
                }
            }
        }
        return dp[0][0][len];
    }
}

---

输出