Poison

87. Scramble String

发表于 
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
class Solution {
    public boolean isScramble(String s1, String s2) {
        char[] chars1 = s1.toCharArray();
        char[] chars2 = s2.toCharArray();

        Map<String, Boolean> cacheMap = new HashMap<>();
        return isScramble(chars1, 0, chars2, 0, s1.length(), cacheMap);
    }

    private boolean isScramble(char[] chars1, int i, char[] chars2, int j, int length, Map<String, Boolean> cacheMap) {
        if (length == 1) {
            return chars1[i] == chars2[j];
        }

        String cacheKey = generateCacheKey(i, j, length);
        Boolean cacheResult = cacheMap.get(cacheKey);
        if (Objects.nonNull(cacheResult)) {
            return cacheResult;
        }

        boolean equals = equals(chars1, i, chars2, j, length);
        if (!equals) {
            cacheMap.put(cacheKey, Boolean.FALSE);
            return false;
        }

        // 至此两个子字符串中的字符可能相等，继续递归判断
        for (int k = 1; k < length; k++) {
            // k 表示前 k 个字符，注意不能等于 length 个字符，因为前 length 个字符等于没有拆分
            if (isScramble(chars1, i, chars2, j, k, cacheMap) // chars1 与 chars2 前 k 个字符是否能进行匹配
                    && isScramble(chars1, i + k, chars2, j + k, length - k, cacheMap)) { // chars1 与 chars2 后 length - k 个字符是否能进行匹配
                cacheMap.put(cacheKey, Boolean.TRUE);
                return true;
            }
            if (isScramble(chars1, i, chars2, j + length - k, k, cacheMap) // chars1 前 k 个字符与 chars2 后 k 个字符是否能进行匹配
                    && isScramble(chars1, i + k, chars2, j, length - k, cacheMap)) { // chars1 后 length - k 个字符与 chars2 前 length - k 个字符是否能进行匹配
                cacheMap.put(cacheKey, Boolean.TRUE);
                return true;
            }
        }

        cacheMap.put(cacheKey, Boolean.FALSE);
        return false;
    }

    private String generateCacheKey(int i, int j, int length) {
        return String.join("_", String.valueOf(i), String.valueOf(j), String.valueOf(length));
    }

    private boolean equals(char[] chars1, int i, char[] chars2, int j, int length) {
        int[] counts1 = new int[26];
        for (int m = i; m < i + length; m++) {
            counts1[chars1[m] - 'a']++;
        }

        int[] counts2 = new int[26];
        for (int m = j; m < j + length; m++) {
            counts2[chars2[m] - 'a']++;
        }

        for (int m = 0; m < 26; m++) {
            if (counts1[m] != counts2[m]) {
                return false;
            }
        }

        return true;
    }
}

索引计算需要注意，容易出错。

Reference

87. Scramble String