leetcode-scramble-string

发表于   |   分类于 ，   |  

题目大意

　　https://leetcode.com/problems/scramble-string/

　　一个字符串可以在中间任意的位置分割成两个非空串，每个非空串可以继续如此操作下去。对形成的树的任意非叶子结点可以进行交换两个子节点，最后所有叶子结点从左向右就形成了一个新串，现在给你两个字符串s1和s2，判断是否属于这种关系。

题目分析

　　动态规划，可以用记忆化搜索实现，我写的版本不是最佳答案，我用了三维数组做记忆，第一维是s1的下标，第二维是s2的下标，第三维是字符串的长度。注意实现细节上，要对分割点进行枚举，同时要考虑调换的情况。然后有些小的优化的地方可以看下代码注释。

代码

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
public class Solution {
    
    private char[] c1;
    private char[] c2;
    private int len;
    private int[][][] f; //记忆结果，1代表true，2代表false
    
    private boolean search(int idx1, int idx2, int l) { // [idx1, idx1 + l - 1] [idx2, idx2 + l - 1]
        if (l == 1) {
            return c1[idx1] == c2[idx2];
        }
        if (f[idx1][idx2][l] > 0) {
            return f[idx1][idx2][l] == 1;
        }
        
        // 剪枝优化
        int[] flag = new int[256];
        for (int i = idx1; i < idx1 + l; i++) {
            flag[c1[i]]++;
        }
        for (int i = idx2; i < idx2 + l; i++) {
            flag[c2[i]]--;
        }
        for (int i = 0; i < 256; i++) {
            if (flag[i] != 0) {
                f[idx1][idx2][l] = 2;
                return false;
            }
        }
        
        for (int i = 0; i < l - 1; i++) { // 枚举分割点，在i之后进行分割
            boolean ans1 = false, ans2 = false;
            
            boolean v1 = search(idx1, idx2, i + 1);
            if (v1) { 
                boolean v2 = search(idx1 + i + 1, idx2 + i + 1, l - i - 1);
                ans1 = v2;
            } else { //优化，不满足直接置为false
                ans1 = false;
            }
            if (ans1) {
                f[idx1][idx2][l] = 1;
                return true;
            }
            
            boolean v3 = search(idx1, idx2 + l - 1 - i, i + 1);
            if (v3) {
                boolean v4 = search(idx1 + i + 1, idx2, l - i - 1);
                ans2 = v4;
            } else { //优化，不满足直接置为false
                ans2 = false;
            }
            if (ans2) {
                f[idx1][idx2][l] = 1;
                return true;
            }
        }
        f[idx1][idx2][l] = 2;
        return false;
    }
    
    public boolean isScramble(String s1, String s2) {
        c1 = s1.toCharArray();
        c2 = s2.toCharArray();
        len = c1.length;
        f = new int[len][len][len + 1];
        return search(0, 0, len);
    }
}

　　复杂度：O(n ^ 4)