// Source : https://oj.leetcode.com/problems/scramble-string/
// Author : Hao Chen
// Date : 2014-10-09
/**********************************************************************************
*
* 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.
*
*
**********************************************************************************/
#include
#include
#include
#include
#include
#include
using namespace std;
// The recursive way is quite simple.
// 1) break the string to two parts:
// s1[0..j] s1[j+1..n]
// s2[0..j] s2[j+1..n]
// 2) then
// isScramble(s1[0..j], s2[0..j]) && isScramble(s1[j+1..n], s2[j+1..n])
// OR
// isScramble(s1[0..j], s2[j+1, n]) && isScramble(s1[j+1..n], s2[0..j])
bool isScramble_recursion(string s1, string s2) {
if (s1.size()!= s2.size() || s1.size()==0 || s2.size()==0) {
return false;
}
if (s1 == s2){
return true;
}
string ss1 = s1;
string ss2 = s2;
sort(ss1.begin(), ss1.end());
sort(ss2.begin(), ss2.end());
if (ss1 != ss2 ) {
return false;
}
for (int i=1; i > > dp(len+1, vector< vector >(len, vector(len) ) );
// ignor the k=0, just for readable code.
// initialization k=1
for (int i=0; i2){
s1 = argv[1];
s2 = argv[2];
}
cout << s1 << ", " << s2 << endl;
cout << isScramble(s1, s2) << endl;
return 0;
}