LC87: Scramble String

작성일

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

  • 문제의 조건을 만족하기 위해서는, 두 단어가 같은 구성으로 되어 있어야 한다.
  • 그래서 두 단어를 같은 크기로 반으로 자르고, 각 단어에서 나오는 조각으로 Recursive Call을 하면 된다.
  • 같은 방향으로, 또는 다른 방향으로 쪼갤 수 있다.
  • substr를 이용하면 TLE가 난다.
  • index를 이용해서 재귀를 구성하면 최악의 경우 $O(N^3 * N)$ 안에 해를 구할 수 있다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    string s1;
    string s2;
    vector<vector<vector<int>>> dp;
public:
    bool isScramble(string s1, string s2) {
        dp.resize(s1.size(), vector<vector<int>>(s1.size(), vector<int>(s1.size(), -1)));
        this->s1 = s1;
        this->s2 = s2;
        return go(0, 0, s2.size());
    }

    bool go(int p1, int p2, int len) {
        if(len == 1) return s1[p1] == s2[p2];
        if(dp[p1][p2][len-1] != -1) return dp[p1][p2][len-1];
        for(int i = 1; i < len; i++) {
            if(go(p1, p2, i) && go(p1+i, p2+i, len-i))
                return dp[p1][p2][len-1] = true;
            if(go(p1, p2+len-i, i) && go(p1+i, p2, len-i))
                return dp[p1][p2][len-1] = true;
        }
        return dp[p1][p2][len-1] = false;
    }
};