【Scramble String】cpp

题目：

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.

代码：

class Solution {
public:
    bool isScramble(string s1, string s2) {
            const int n1 = s1.size();
            const int n2 = s2.size();
            if (n1!=n2) { return false; }
            const int n = n1;
            int alpha[26] = {0};
            for ( int i=0; i<n; ++i ){ alpha[s1[i]-'a']++; alpha[s2[i]-'a']--; }
            for ( int i=0; i<26; ++i ){ if ( alpha[i]!=0 ) return false; }
            // terminal condition
            if ( n==1 ) return s1[0]==s2[0];
            // recursive process
            for ( int i=1; i<n; ++i ){
                //cout << s1 << "," << s2 << ":" << i << endl;
                if (
                    (
                        Solution::isScramble(s1.substr(0,i), s2.substr(0,i)) && 
                          Solution::isScramble(s1.substr(i,n-i), s2.substr(i,n-i)) 
                    )
                       ||
                    (
                        Solution::isScramble(s1.substr(0,i), s2.substr(n-i,i)) && 
                          Solution::isScramble(s1.substr(i,n-i), s2.substr(0,n-i))
                    )
                   )
                   { return true; }
            }
            return false;
    }
};

tips：

这道题的题意自己并没有理解好，引用一个网上其他人的理解如下：

（http://www.blogjava.net/sandy/archive/2013/05/22/399605.html）

由于一个字符串有很多种二叉表示法，貌似很难判断两个字符串是否可以做这样的变换。
“对付复杂问题的方法是从简单的特例来思考，从而找出规律。
先考察简单情况：
字符串长度为1：很明显，两个字符串必须完全相同才可以。
字符串长度为2：当s1="ab", s2只有"ab"或者"ba"才可以。
对于任意长度的字符串，我们可以把字符串s1分为a1,b1两个部分，s2分为a2,b2两个部分，满足（(a1~a2) && (b1~b2)）或者 （(a1~b2) && (a1~b2)）”

理解了题意，代码也就写出来了。

具体还有几个细节需要注意：

1. 为了剪枝并加快速度，做了如下几件事情：

　　a) 判断s1与s2的长度是否相等

　　b) 判断s1与s2的每个字符数量是否相等（这里由于是字母所以用一个定长数组alpha[26]表示：某个字母在s1中出现一次+1，在s2中出现一次-1；最终alpha的每个元素都是0则证明s1与s2的每个字符数量相等。扩展一下，如果字符不止26个字母，包含其他字符呢？可以用hashmap表示）

2. 设定终止条件：

　　如果s1和s2长度已经为1，无法再分割了，就直接比较即可。

3. 在递归传入参数的时候，用到了substr(begin, num)：

　　a) begin代表切取的第一个字符下标，num代表截取几个字符

　　b) 注意每次传入isScramble的字符长度相等

===========================================

上述的做法类似记忆化搜索，网上还有一种动态规划的解法，也学习了吧。

（http://blog.csdn.net/linhuanmars/article/details/24506703）

class Solution {
public:
    bool isScramble(string s1, string s2) {
            const int n1 = s1.size();
            const int n2 = s2.size();
            if ( n1 != n2 ) return false;
            const int n = n1;
            vector<vector<vector<bool> > > dp(n,vector<vector<bool> >(n,vector<bool>(n+1,false)));
            for ( int k=1; k<=n; ++k )
            {
                for ( int i=0; i<=n-k; ++i )
                {
                    for ( int j=0; j<=n-k; ++j )
                    {
                        if ( k==1 ) 
                        {
                            dp[i][j][k] = s1[i]==s2[j];
                            continue;
                        }
                        for ( int l=1; l<k; ++l )
                        {
                            dp[i][j][k] = 
                            (dp[i][j][l] && dp[i+l][j+l][k-l])
                            ||
                            (dp[i][j+k-l][l] && dp[i+l][j][k-l]);
                            if ( dp[i][j][k] ) break;
                        }
                    }
                }
            }
            /*
            for ( int k=0; k<=n; ++k )
            {
                cout << k << endl;
                for ( int i=0; i<n; ++i)
                {
                    for (int j=0; j<n; ++j )
                    {
                        cout << dp[i][j][k] << " ";
                    }
                    cout << endl;
                }
            }
            */
            return dp[0][0][n];
    }
};

tips：

AC之后发现这道题的dp思路其实可以由递归思路得来。

递归算法在不断的递归过程中，其实是一直再算s1的某一段与s2等长的某一段是否符合scramble的特点；注意，这里的某一段不一定指的是s1和s2从同一个位置开始。递归过程中，并没有记录这样的s1、s2字串比较的历史信息；而dp的解法是比较一次记录一次比较的历史信息，下次再判断的时候就可以利用上历史的比较信息了。

dp的过程（http://blog.csdn.net/linhuanmars/article/details/24506703）已经说的很好了。

这里有个细节需要注意一下，就是最外层的循环k代表从s1和s2截取字符串的长度。这里为了在下标表示方便，定义为n+1维；这样的好处就在于循环中的k直接表示的就是需要比较的子字符串的长度，不用考虑k-1这一类的内容。

这题的dp思路太精妙，只能学习膜拜。

完毕。

===================================================

第二次过这道题，dp的做法没时间去过了，用“深搜+剪枝”的做法更直观一些。

class Solution {
public:
    bool isScramble(string s1, string s2) {
            if ( s1.size()!=s2.size() ) return false;
            int count[256] = {0};
            for ( int i=0; i<s1.size(); ++i ){
                count[(int)s1[i]]++;
                count[(int)s2[i]]--;
            }
            for ( int i=0; i<256; ++i ) { if ( count[i]!=0 ) return false; }
            if ( s1.size()==1 ) return s1[0]==s2[0];
            for ( int l=1; l<s1.size(); ++l ){
                bool possible = Solution::isScramble(s1.substr(0,l), s2.substr(0,l)) &&
                                 Solution::isScramble(s1.substr(l, s1.size()-l), s2.substr(l, s2.size()-l));
                if ( possible ) return true;
                possible = Solution::isScramble(s1.substr(0,l), s2.substr(s2.size()-l,l)) &&
                           Solution::isScramble(s1.substr(l,s1.size()-l), s2.substr(0,s2.size()-l));
                if ( possible ) return true;
            }
            return false;
    }
};