LeetCode 87. Scramble String

Posted on Edited on In 
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
class Solution {
private:
    int memo[30][30][31]; // -1 as false, 1 as true, 0 as uncalculated.
    string s1, s2;
    bool checkIfSimilar(int i1, int i2, int len) {
        unordered_map<int, int> freq;
        for (int i = i1; i < i1 + len; ++i)
            ++freq[s1[i]];
        for (int i = i2; i < i2 + len; ++i)
            if (--freq[s2[i]] < 0)
                return false;
        return true;
    }
    bool dfs(int i1, int i2, int len) {
        if (memo[i1][i2][len])
            return memo[i1][i2][len] == 1;
        if (s1.substr(i1, len) == s2.substr(i2, len)) {
            memo[i1][i2][len] = 1;
            return true;
        }
        if (!checkIfSimilar(i1, i2, len)) {
            memo[i1][i2][len] = -1;
            return false;
        }
        for (int i = 1; i < len; ++i) {
            if ((dfs(i1, i2, i) && dfs(i1 + i, i2 + i, len - i))
                || (dfs(i1, i2 + len - i, i) && dfs(i1 + i, i2, len - i))) {
                memo[i1][i2][len] = 1;
                return true;
            }
        }
        memo[i1][i2][len] = -1;
        return false;
    }
public:
    bool isScramble(string s1, string s2) {
        memset(memo, 0, sizeof(memo));
        this->s1 = s1;
        this->s2 = s2;
        return dfs(0, 0, s1.size());
    }
};