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.

分析：动态规划，dp[i][j][k]表示s1[i~i+len]与s2[j~j+len]是否为Scramble String，即S1从i开始k个字符与S2从j开始k个字符是否为Scramble String。对于每一个分割点，分别判断左右两侧是否是Scramble String，如果有一个满足，则该子串就满足Scramble String，即

dp[i][j][len] = (dp[i][j][k] && dp[i+k][j+k][len-k]) || (dp[i][j+len-k][k] && dp[i+k][j][len-k])，当len==1时，dp[i][j][1] = s1[i] == s2[j].

class Solution {
public:
    bool isScramble(string s1, string s2)
    {
        int length = s1.size(),i,j,k,len;
        if(length != s2.size())return false;
        vector< vector< vector<bool> > >dp(length);
        for (i = 0;i < length;++i)
        {
        	vector< vector<bool> >tmp1(length);
        	for (j = 0;j < length;j++)
        	{
        		vector<bool> tmp2(length+1,false);
        		tmp1[j] = tmp2;
        	}
        	dp[i] = tmp1;
        }
        for (len = 1;len <= length;len++)
        {
        	for (i = 0;i + len <= length;++i)
        	{
        		for (j = 0;j +len <= length;++j)
        		{
        			if (len == 1)dp[i][j][len] = (s1[i] == s2[j]);
        			else
        			{
        				for (k = 1;k < len;k++)
        				{
        					if ((dp[i][j][k] && dp[i+k][j+k][len-k]) || (dp[i][j+len-k][k] && dp[i+k][j][len-k]))
        					{
        						dp[i][j][len] = true;//表示s1[i~i+len]与s2[j~j+len]是否为Scramble String
        						break;
        					}
        				}
        			}
        		}
        	}
        }
        return dp[0][0][length];
    }
};

leetcode 之 Scramble String