ok

NoteXYX · NoteXYX · commit d8c4b7c41e96 · 2020-09-12T09:50:44.000+08:00
diff --git a/src/com/leetcode/Main87.java b/src/com/leetcode/Main87.java
@@ -0,0 +1,62 @@
+package com.leetcode;
+
+/**
+ * 87. 扰乱数组
+ * 给定一个字符串 s1，我们可以把它递归地分割成两个非空子字符串，从而将其表示为二叉树。
+ *
+ * 下图是字符串 s1 = "great" 的一种可能的表示形式。
+ *
+ *     great
+ *    /    \
+ *   gr    eat
+ *  / \    /  \
+ * g   r  e   at
+ *            / \
+ *           a   t
+ * 在扰乱这个字符串的过程中，我们可以挑选任何一个非叶节点，然后交换它的两个子节点。
+ *
+ * 例如，如果我们挑选非叶节点 "gr" ，交换它的两个子节点，将会产生扰乱字符串 "rgeat" 。
+ */
+public class Main87 {
+    public boolean isScramble(String s1, String s2) {
+        char[] chs1 = s1.toCharArray();
+        char[] chs2 = s2.toCharArray();
+        int n = s1.length();
+        int m = s2.length();
+        if (n != m) {
+            return false;
+        }
+        boolean[][][] dp = new boolean[n][n][n + 1];
+        // 初始化单个字符的情况
+        for (int i = 0; i < n; i++) {
+            for (int j = 0; j < n; j++) {
+                dp[i][j][1] = chs1[i] == chs2[j];
+            }
+        }
+
+        // 枚举区间长度 2～n
+        for (int len = 2; len <= n; len++) {
+            // 枚举 S 中的起点位置
+            for (int i = 0; i <= n - len; i++) {
+                // 枚举 T 中的起点位置
+                for (int j = 0; j <= n - len; j++) {
+                    // 枚举划分位置
+                    for (int k = 1; k <= len - 1; k++) {
+                        // 第一种情况：S1 -> T1, S2 -> T2
+                        if (dp[i][j][k] && dp[i + k][j + k][len - k]) {
+                            dp[i][j][len] = true;
+                            break;
+                        }
+                        // 第二种情况：S1 -> T2, S2 -> T1
+                        // S1 起点 i，T2 起点 j + 前面那段长度 len-k ，S2 起点 i + 前面长度k
+                        if (dp[i][j + len - k][k] && dp[i + k][j][len - k]) {
+                            dp[i][j][len] = true;
+                            break;
+                        }
+                    }
+                }
+            }
+        }
+        return dp[0][0][n];
+    }
+}
