Created
November 2, 2013 17:42
-
-
Save zsh-89/7281493 to your computer and use it in GitHub Desktop.
Leetcode: Scramble String
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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_; | |
}; |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
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