23.03.30. 풀었던 문제들

Leetcode 87. Scramble String

 어떤 string s1에 특정 연산을 반복해 s2를 만들 수 있는지 문제. DP 문제이다. 

 

 기본적인 직관은 s1의 substring이 s2의 scramble인지 확인하는 것이다. 또한, s1의 각 index에 대해 앞/뒤의 단어를 자르고, 또 앞뒤 단어를 바꿀 수 있기에 이를 모두 계산해 보면 된다.

 

 top-down으로 풀 때, s1의 index를 기준으로 s1, s2를 쪼개고 각각의 subproblem 4개를 풀 수 있다.

• base case : s1 == s2이면 return true
• s1의 앞쪽 substring과 s2의 앞쪽 substring && s1의 뒤쪽 substring과 s2의 뒤쪽 substring ... 1번, 2번
• 순서를 바꾼 s1의 앞쪽 substring과 s2의 앞쪽 substring && 순서를 바꾼 s1의 뒤쪽 substring과 s2의 뒤쪽 substring ... 3번, 4번
• (1번 && 2번) || (3번 && 4번) return true;

 이렇게 4개의 subproblem을 풀고, 1번 && 2번, 또는 3번 && 4번이 true이면 s1에 연산을 가해 s2를 만들 수 있다는 말이다. 예를 들어

s1 = great, s2 = rgeat

i = 1일 때
s1을 g / reat로 쪼개면 s1은 g / reat와 reat / g의 형태를 가질 수 있다. 따라서 
s1 : g / reat, s2 : r / geat
s1 : reat / g, s2 : rgea / t
이렇게 쪼개고 각각의 subproblem을 풀면 된다.

i = 2일 때
s1을 gr / eat로 쪼개면 s1은 gr / eat와 eat / gr의 형태를 가질 수 있다. 따라서 
s1 : gr / eat, s2 : rg / eat
s1 : eat / gr, s2 : rge / at
이렇게 쪼개고 각각의 subproblem을 풀면 된다.

 

 그러나 이렇게 풀면 T(n) = 4T(n-1) + O(n)이다. 약 O(n!)이다. n=30이므로 불가능. 그래서 memoization을 해야 한다. 이미 계산한 값이라면 계산하지 않도록. 일반적인 memoization이라면 dp[i][j]와 같은 배열을 사용하겠지? 그러나 이 문제의 경우 [s1의 시작점, s1의 끝점, s2의 시작점, s2의 끝점] 이렇게 4개의 index가 들어가므로 4차원 dp 배열을 만들어야 한다. 귀찮으므로 map을 하나 만들어서 퉁치면 쉽게 풀 수 있다.

 

// Runtime 177 ms Beats 39.14%
// Memory 37.1 MB Beats 32.82%

class Solution {
public:
    unordered_map<string, bool> um;

    bool isScramble(string s1, string s2) {
        if(s1 == s2) return true;

        string key = s1 + " " + s2;
        if(um.find(key) != um.end()) return um[key];

        for(int len = 1; len<s1.length(); len++){
            // x + y
            bool xy = isScramble(s1.substr(0, len), s2.substr(0, len)) && isScramble(s1.substr(len), s2.substr(len));
            
            if(xy){
                um[key] = true;
                return true;
            }   

            //isScramble(s1.substr(0, len), s2.substr(0, len)); // s1 앞부분, s2 앞부분
            //isScramble(s1.substr(len), s2.substr(len)); // s1 뒷부분, s2 뒷부분

            // y + x
           bool yx = isScramble(s1.substr(0, len), s2.substr(s2.length() - len)) && isScramble(s1.substr(len), s2.substr(0, s2.length() - len));
            if(yx){
                um[key] = true;
                return true;
            }
            //isScramble(s1.substr(0, len), s2.substr(s2.length() - len)); // s1의 앞부분, s2 뒷부분
            //isScramble(s1.substr(len), s2.substr(0, s2.length() - len)); // s1의 앞부분, s2 앞부분
        }
        um[key] = false;
        return false;
    }
};

 

시간복잡도

 [s1의 시작점, s1의 끝점, s2의 시작점, s2의 끝점]에 대해 각각 모든 연산을 하므로 O($n^{4}$)이다.

 

공간복잡도

 map에 들어가는 것은 해당 recurse의 개수와 동일할 것이다. 따라서 O(n^4).

 

후기

 상당히 어려웠다. 어떻게 똮! 하고 점화식을 내서 풀었는데 어떻게 풀었는제 모르겠다. 다음에 한 번 더 풀어봐야지.