【LeetCode】87. Scramble String 해법 및 설명

87. Scramble String
Total Accepted: 44881 Total Submissions: 170059 Difficulty: Hard
Given a string s1, we may represent it as a binary tree by partitioning it to two non-empty substrings recursively.
Below is one possible representation of s1 =  "great" :

    great
   /    \
  gr    eat
 / \    /  \
g   r  e   at
           / \
          a   t

To scramble the string, we may choose any non-leaf node and swap its two children.
For example, if we choose the node  "gr"  and swap its two children, it produces a scrambled string  "rgeat" .

    rgeat
   /    \
  rg    eat
 / \    /  \
r   g  e   at
           / \
          a   t

We say that  "rgeat"  is a scrambled string of  "great" .
Similarly, if we continue to swap the children of nodes  "eat"  and  "at" , it produces a scrambled string  "rgtae" .

    rgtae
   /    \
  rg    tae
 / \    /  \
r   g  ta  e
       / \
      t   a

We say that  "rgtae"  is a scrambled string of  "great" .
Given two strings s1 and s2 of the same length, determine if s2 is a scrambled string of s1.
[분석]
제목은 한 문자열이 다른 문자열의'난서'로 얻어졌는지 판단하는 데 있다. 이런 난서는 한 문자열을 특정한 위치에서'잘라내서'두 개의 자열을 형성한 다음에 두 개의 자열을 똑같이 잘라서 잎 노드에 도달할 때까지 분할할 수 없도록 하는 방식을 사용한다.그리고 비잎 노드의 좌우 아이 노드를 교환하고 마지막으로 다시 왼쪽에서 오른쪽으로 조합하여 새로운 문자열을 형성한다. 이 과정에서 문자 위치의 변화가 존재하기 때문에 원래의 문자열 순서가 혼란스러울 수도 있고 당연히 없을 수도 있다(같은 비잎 노드의 좌우 아이는 0번 또는 짝수 번을 교환하면 변화가 없다).주의해야 할 점:
1. 원래 문자열이 매번 베어지는 위치가 [1,s.size()-1]일 수 있으므로 베어질 수 있는 모든 위치를 옮겨야 한다.
2. 원래 문자열은 i의 첫 번째 위치에서 잘려진다(i는 구간[1,s.size()-1]). 형성된 두 개의 자열은 s.substr(0,i)와 s.substr(i,s.size()-i)이다. 만약에 이 두 개의 자열이 모두 비어 있지 않으면 그들의 모열(여기는 원래 문자열을 가리킨다)은 이른바 비잎 노드이고 이 두 개의 자열은 좌우로 교환할 수 있다(이차 나무의 전개 방식에 따라).두 개의 자열에 대해서는 잎 노드가 형성될 때까지 계속 갈라질 수 있다.
3. 원문자열에 대응하는'난서'열 s1은 다음과 같은 규칙을 충족시킨다. 만약'난서'열을 i의 위치에서 똑같이 자르면 그 역시 두 개의 자열을 형성할 수 있다. s1.substr(0,i)와 s1.substr(i, s1.size()-i), 만족:
  s1.substr(0,i)는 s.substr(0,i)의'난서'이며 s1.substr(i, s1.size()-i)는 s.substr(i, s.size()-i)의 "난서"입니다
또는 (좌우 교환 때문에)
  s1.substr(0,i)는 s.substr(s.size()-i)의'난서'및 s1입니다.substr(i)는 s.substr(0,s.size()-i)의'난서'입니다.
4. 위에서 분석한 바와 같이 우리는 큰 문제를 작은 문제로 분해할 수 있다. 귀속 호출을 통해 두 문자열이 서로'난서'인지 아닌지를 판단할 수 있다. 그리고 주의해야 할 문제는 바로'가지치기'작업이다. 두 갈래 나무의 형식이 분해되고 차원이 깊다. 각 층은 (3) 중의 두 가지 가능성 중 하나를 만족시켜야 한다. 만족하지 않으면 다음 층을 계속하지 않고false로 되돌아간다. 이것이 바로 가지치기 작업이다.효율을 극대화할 수 있다.
5.'가지'제약. 만약에 두 문자열 s1과 s2가 서로'난서'라면 s1과 s2가 포함하는 문자와 수량을 만족시켜야 한다. 만약에 다르면'난서'를 구성할 수 없기 때문에 이 조건은 가지치기 조건으로 할 수 있다.
6. 두 가지 도구: 두 문자열이 완전히 같은 자모를 포함하고 있는지 판단하기 위해'해시표'를 사용한다.STL 함수:substr(i,n)에 사용된 하위 문자열 나누기;문자열이 i번째 위치에서 시작하는 n자를 나타냅니다. n이 비어 있으면 기본적으로 문자열의 끝까지입니다.
[해법 및 주석]

class Solution {
public:
    bool isScramble(string s1, string s2) {
        
        if(s1.size()!=s2.size())return false;
        if(s1==s2)return true;
        vector<int> hash(26,0);
        
        for(int i=0;i<s1.size();i++)
        hash.at(s1[i]-'a')++;
        
        for(int j=0;j<s2.size();j++)
        hash.at(s2[j]-'a')--;
        
        for(int k=0;k<26;k++)
        {
            if(hash.at(k)!=0)
            return false;
        }
        
        for(int i=1;i<s1.size();i++)
        {
            if(
                (isScramble(s1.substr(0, i), s2.substr(0, i)) && isScramble(s1.substr(i,s1.size()-i), s2.substr(i,s1.size()-i)))
             || (isScramble(s1.substr(0, i), s2.substr(s1.size()-i)) && isScramble(s1.substr(i), s2.substr(0, s1.size()-i)))
              )
                return true;

        }
        return false;
    }
};