LeetCode每日一题：乱串

问题描述

Given a string s1, we may represent it as a binary tree by partitioning it to two non-empty substrings recursively.
Below is one possible representation of s1 ="great":
great
/
gr eat
/ \ /
g r e at
/
a t
To scramble the string, we may choose any non-leaf node and swap its two children.
For example, if we choose the node"gr"and swap its two children, it produces a scrambled string"rgeat".
rgeat
/
rg eat
/ \ /
r g e at
/
a t
We say that"rgeat"is a scrambled string of"great".
Similarly, if we continue to swap the children of nodes"eat"and"at", it produces a scrambled string"rgtae".
rgtae
/
rg tae
/ \ /
r g ta e
/
t a
We say that"rgtae"is a scrambled string of"great".
Given two strings s1 and s2 of the same length, determine if s2 is a scrambled string of s1.

问题分析

这题的意思是将字符串写成二叉树的情况，若经过子树经过交换的变换可以相等的话，那么return true。
这题适宜用动态规划来做
设 dp[k][i][j] 表示s1从第i个字符开始、s2从第j个字符开始，长度为k的子串是否是乱串。
比较难说明，具体的可以看代码里的解释了

代码实现

public boolean isScramble(String s1, String s2) {
        if (s1.length() != s2.length()) return false;
        int len = s1.length();
        boolean[][][] dp = new boolean[len + 1][len + 1][len + 1];
        for (int i = 0; i < len; i++) {
            for (int j = 0; j < len; j++) {
                if (s1.charAt(i) == s2.charAt(j))
                    dp[1][i][j] = true;
                else dp[1][i][j] = false;
            }
        }
        for (int k = 2; k <= len; ++k) {
            for (int i = 0; i <= len - k; ++i) {
                for (int j = 0; j <= len - k; ++j) {
                    //div表示长度为k的子串中，将子串一分为二的分割点
                    for (int div = 1; div < k && !dp[k][i][j]; ++div) {
                        // dp[k][i][j] = true的条件是子串分割后的两段对应相等，或者交叉对应相等
                        if ((dp[div][i][j] && dp[k - div][i + div][j + div])
                                || (dp[div][i][j + k - div] && dp[k - div][i + div][j])) {
                            dp[k][i][j] = true;
                        }
                    }
                }
            }
        }
        return dp[len][0][0];
    }