【C++】 LeetCode 87. Scramble String

题目：

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.

运行结果：

解析：

题意：判断两个字符串是否能通过二叉树的左右子树交换相等

思路：

这题最简单的方法就是直接用递归，暴力求解， 把s1，s2分别分成两部分，判断s1的两部分和s2的两部分是否分别可以交换相等。但是提交会超时。 超时的原因是很多比较是重复进行的，导致运算量过大。故可以采用动态规划的思想把中间结果保存起来直接调用，就可以减少重复计算了。由于此题是两个字符串，故记录结果需要用到三维数组iscmp[i][j][len]表示s1以i作为起始位，长度为len的字符串和s2以j作为起始位，长度为len的字符串是否可以交换相等。三维数组默认值均为0，则可以采用1表示可交换，-1表示不可交换，就可以不用对三位数组进行初始化了（默认值都为0）

代码：

class Solution {
public:
    bool findscram(string &s1, string &s2,int i1,int i2,int len,vector<vector<vector<int>>> &iscmp){
        if(i1>s1.size()||i2>s2.size()){
            if(i1>=s1.size()&&i2>=s2.size())return true;
            else return false;
        }
        if(iscmp[i1][i2][len]==1) return true;
        else if(iscmp[i1][i2][len]==-1) return false;
        
        if(len==1){
            if(s1[i1]==s2[i2]){
                iscmp[i1][i2][len]=1;
                return true;
            }
            else{
                iscmp[i1][i2][len]=-1;
                return false;
            }
        }
        for(int i=1;i<len;i++){
            if(findscram(s1,s2,i1,i2,i,iscmp)&&findscram(s1,s2,i1+i,i2+i,len-i,iscmp)){
                iscmp[i1][i2][len]=1;
                return true;
            }
            if(findscram(s1,s2,i1,i2+len-i,i,iscmp)&&findscram(s1,s2,i1+i,i2,len-i,iscmp)){
                iscmp[i1][i2][len]=1;
                return true;
            }
        }
        iscmp[i1][i2][len]=-1;
        return false;
    }
    bool isScramble(string s1, string s2) {
        int len1=s1.size();
        int len2=s2.size();
        if(len1!=len2)return false;
        if(len1==0) return true;
        vector<vector<vector<int>>> iscmp(len1+1,vector<vector<int>>(len1+1,vector<int>(len1+1,0)));
        return findscram(s1,s2,0,0,len1,iscmp);
    }
};