Leetcode(87) Scramble String

发表于 | 分类于

Description

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":

1
2
3
4
5
6
7
    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".

1
2
3
4
5
6
7
    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".

1
2
3
4
5
6
7
    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.

Example 1:

1
2
Input: s1 = "great", s2 = "rgeat"
Output: true

Example 2:

1
2
Input: s1 = "abcde", s2 = "caebd"
Output: false

解法

很明显的一道动态规划的题，先解释一下动态规划的渊源。

一般动态规划可解的题都是分治递归可解的，我们不难发现，分治算法之所以理论复杂度很高，其原因是因为重复的进行了很多子问题的计算，这是不必要的，如果我们一旦计算出某个子问题的结果，就将其存在内存中，下次要用到的时候，我们就直接使用不再次进行计算的话，这样是不是就能够减少很多复杂度呢？

实际上，这样的方法被称作“记忆化”，即将已经发生过的计算的结果记忆下来，以待之后使用。

特别的，由于运算过程中保证小的子问题需要先进行运算，我们可以不用递归来进行这样的计算，而是按照从小到大的顺序依次将所有的子问题计算出来，由于小的子问题先得到计算，所以我们可以确保在计算某一个之后的问题时，它需要的所有子问题都已经得到了计算。

这样的方法，被称作动态规划，这也是为什么常有人说动态规划和记忆化是非常类似的算法的原因了。

在实现中，其实就和分治算法非常类似，不过是将递归的过程改成了递推。

回到题目本身，题目的问题可以这样分析，就是s1和s2是scramble的话，那么必然存在一个在s1上的长度l1，将s1分成s11和s12两段，同样有s21和s22.那么要么s11和s21是scramble的并且s12和s22是scramble的；要么s11和s22是scramble的并且s12和s21是scramble的。

i，j，代表字符串的开始位置，len代表比较的长度，在len内按照长度k进行分割

递归式为：

1
dp[i][j][len] = || (dp[i][j][k] && dp[i + k][j + k][len - k]) || (dp[i + k][j][len - k] && dp[i][j + len - k][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
36
37
38
39
class Solution {
    public boolean isScramble(String s1, String s2) {
        if (s1.length() != s2.length()) {
            return false;
        }
        if (s1.equals(s2)) {
            return true;
        }
        int n = s1.length();
        Boolean[][][] res = new Boolean[n][n][n + 1];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                for (int k = 0; k <= n; k++) {
                    res[i][j][k] = false;
                }
            }
        }
        //初始化边界值：
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                res[i][j][1] = (s1.charAt(i) == s2.charAt(j));
            }
        }
        //最外层堆len的值进行遍历
        //最内层对len长度下的分割方式进行遍历
        for (int len = 2; len <= n; len++) {
            for (int i = 0; i <= n - len; i++) {
                for (int j = 0; j <= n - len; j++) {
                    for (int k = 1; k < len; k++) {
                        if ((res[i][j][k] && res[i + k][j + k][len - k]) || (res[i + k][j][len - k] && res[i][j + len - k][k])) {
                            res[i][j][len] = true;
                        }
                    }
                }
            }
        }
        return res[0][0][n];
    }
}