87. Scramble String

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

字符串用二叉树表示，每个结点是上个结点递归定义，把二叉树中任意一个非叶结点的两个children swap所形成的新树所代表的字符串为原来的字符串scramble str。递归把所有可能的partition验证一遍，和解决二叉树一样的分治思路。这题还可以用DP，需要三维状态，过于复杂。

/*
 * @lc app=leetcode id=87 lang=cpp
 *
 * [87] Scramble String
 *
 * https://leetcode.com/problems/scramble-string/description/
 *
 * algorithms
 * Hard (32.10%)
 * Likes:    334
 * Dislikes: 539
 * Total Accepted:    95.4K
 * Total Submissions: 296.6K
 * Testcase Example:  '"great"\n"rgeat"'
 *
 * 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.
 * 
 * Example 1:
 * 
 * 
 * Input: s1 = "great", s2 = "rgeat"
 * Output: true
 * 
 * 
 * Example 2:
 * 
 * 
 * Input: s1 = "abcde", s2 = "caebd"
 * Output: false
 * 
 */
class Solution {
public:
    bool isScramble(string s1, string s2) {
         const int N = s1.size();
         if (s2.size() != N) return false;
         if (N == 1) {
            if (s1 == s2) return true;
            return false;
         }
         // check whether is a permutation.
         vector<int> freq(26);
         for (const auto c : s1) --freq[c - 'a'];
         for (const auto c : s2) ++freq[c - 'a'];
         for (int i = 0; i < 26; ++i) {
             if (freq[i] != 0) return false;
         }
         // divide and conquer 
         for (int i = 1; i < N; ++i) {
             const string s1l = s1.substr(0, i);
             const string s1r = s1.substr(i);
             if (isScramble(s1l, s2.substr(0, i)) && isScramble(s1r, s2.substr(i)) ||
             isScramble(s1l, s2.substr(N - i)) && isScramble(s1r, s2.substr(0, N - i)))
             return true;
         }
         return false;
    }
};