我感觉word ladder 2的思路比这道题还容易点，算法还比较出名，就是很不好写。。
。。。。。。
yuxrose (鱼香肉丝), 我倒是找到两个比较简洁的答案，但是最烦recursion。。。。
。。我觉得自己都缺乏动力搞懂这个题，也可能今天状态不佳。看答案都不清楚为啥，
都想放弃刷题啦！
但是花时间仔细琢磨，第一个答案好像也不是那么那么难，但第二个就不知道在干嘛了
，搞了3d table。晕啊！哪位大牛能解释一下呢？
如果没见过，谁能15分钟内搞懂题意，到写完代码，估计得下了狠功夫的。
这个有recursion还比没有recursion的快！
class Solution {
private:
bool isDeformation(string &s1, string &s2)
{
if(s1.size() != s2.size())return false;
int albe[26] = {0};
for(int i = 0; i < s1.size(); i ++)
albe[s1[i] - 'a'] ++;
for(int i = 0; i < s2.size(); i ++)
{
albe[s2[i] - 'a'] --;
if(albe[s2[i] - 'a'] < 0)return false;
}
return true;
}
public:
bool isScramble(string s1, string s2) {
if(isDeformation(s1, s2))
{
int len = s1.size();
if(len <= 3) return true;
for(int i = 1; i < s1.size(); i ++)
{
string s11 = s1.substr(0, i);
string s12 = s1.substr(i, len-i);
if(isScramble(s11, s2.substr(0,i)) && isScramble(s12, s2.
substr(i, len-i)))
return true;
if(isScramble(s11, s2.substr(len-i,i)) && isScramble(s12, s2
.substr(0, len-i)))
return true;
}
}
return false;
}
};
class Solution {
public:
bool isScramble(string s1, string s2) {
int len=s1.size();
if (len!=s2.size()) return false;
bool dp[100][100][100]={false};
for (int i=len-1;i>=0;i--)
for (int j=len-1;j>=0;j--) {
dp[i][j][1]=(s1[i]==s2[j]);
for (int l=2;i+l<=len && j+l<=len;l++) {
for (int n=1;ndp[i][j][l]|=dp[i][j][n]&&dp[i+n][j+n][l-n];
dp[i][j][l]|=dp[i][j+l-n][n]&&dp[i+n][j][l-n];
}
}
}
return dp[0][0][len];
}
};
