Leetcode: Scramble String

Scramble String.cpp

class Solution {
public:
	bool isScramble(string s1, string s2) {
		int N = s1.size();
		if (N != s2.size()) return false;
		if (N == 0) return true;

		init(N);  s1_ = &s1;  s2_ = &s2;
		return judge(0, 0, N);
	}
	bool judge(int i, int j, int l) {
		if (l==0) return true;
		if (dp_[i][j][l-1] != 0) return dp_[i][j][l-1]==2;

		string sub1 = s1_->substr(i, l);
		string sub2 = s2_->substr(j, l);
		if (sub1 == sub2) {
			dp_[i][j][l-1] = 2;
			return true;
		}
		sort(sub1.begin(), sub1.end());
		sort(sub2.begin(), sub2.end());
		if (sub1 != sub2) {
			dp_[i][j][l-1] = 1;
			return false;
		}

		for (int k = 1; k <= l-1; ++k) {
			if ( (judge(i, j, k) && judge(i+k, j+k, l-k)) || (judge(i, j+l-k, k) && judge(i+k, j, l-k)) ) {
				dp_[i][j][l-1] = 2;
				return true;
			}
		}
		dp_[i][j][l-1] = 1;
		return false;
	}
	void init(int N) {
		vector<char> x(N, 0);
		vector< vector<char> > y(N, x);
		dp_.assign(N, y);
	}
	vector< vector< vector<char> > > dp_; // 0:not yet calc; 1:fail 2:success
	string *s1_;
	string *s2_;
};

copy来的说明( http://discuss.leetcode.com/questions/262/scramble-string ):
Given a string A and a string B, if B is a scramble string of A, then there must be a way for us to divide B into two parts B1, B2 and A into A1, A2, where B1 contains exactly the same characters (ignore order) as A1 or A2. Otherwise, B won't be a scramble string of A.

然后用dp[N][N][N]来打表
dp[i][j][l-1] 表示 s1[i, i+l-1] 是否能scramble成 s2[j, j+l-1]

感觉自顶向下+sort搜索空间要小
如果把sort那段去掉, 时间从56ms=>76ms
从wiki复制来的纯自底向上也是56ms