ChunNote
0%

leetCode-87:Scramble String

发表于 分类于

问题描述

将一个字符串递归分割，可以用一棵二叉树来表示。将这颗树上非叶子节点的两节点进行交换得到一颗新的二叉树（也是一个新的字符串）。现在给出两个字符串，要求判断第一个字符串是否能经过上述变化（允许多次或者递归变化）得到第二个字符串。题目链接：**点我**

样例输入输出

输入：s1 = “great”, s2 = “rgeat”

输出：true

输入：”abcde”, s2 = “caebd”

输出：false

问题解法

仔细观察分析，可以确定，如果 s1 和 s2 可以相互转换，那么必然存在一个分割点将两个字符串切开，假设 s1 切割为 s11 和 s12， s2 切割为 s21 和 s22，使得 s11 和 s21、s12 和 s22 可以相互转换，或者 s11 和 s22、s12 和 s21 可以相互转换。

因此，可以用动态规划进行求解。假设 dp[i][j][k] 表示 s1 字符串中从 i 位置开始 k 个字符构成的字符串与 s2 字符串中从 j 位置开始 k 个字符构成的字符串两者的转换结果（true 或者 false，能相互转换为 true，否则为 false），则动态转移方程为：dp[i][j][k] = (dp[i][j][m] && dp[i + m][j + m][k - m]) || (dp[i][j + k - m][m] && dp[i + m][j][k - m]) (1 <= m < k)。dp[0][0][length] 的结果就是最终的结果。为了使动态转移方程在计算过程中能够获取到表达式中每个计算项的值（确保表达式中每个计算项在本次计算之前已经得到相应的结果），i、j 的循环需要从后往前，k 的循环从前往后。代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution
{
    public boolean isScramble(String s1, String s2)
    {
        if (s1.length() != s2.length())
        {
            return false;
        }

        int len = s1.length();
        boolean[][][] dp = new boolean[len][len][len + 1];
        for (int i = len - 1; i >= 0; i--)
        {
            for (int j = len - 1; j >= 0; j--)
            {
                for (int k = 1; k <= len - j && k <= len - i; k++)
                {
                    dp[i][j][k] = s1.substring(i, i + k).equals(s2.substring(j, j + k));
                    for (int m = 1; m < k; m++)
                    {
                        boolean temp = dp[i][j][m] && dp[i + m][j + m][k - m];
                        boolean temp2 = dp[i][j + k - m][m] && dp[i + m][j][k - m];
                        dp[i][j][k] = dp[i][j][k] || temp || temp2;
                        if (dp[i][j][k])
                        {
                            break;
                        }
                    }
                }
            }
        }

        return dp[0][0][len];
    }
}