图片.png
//my
class Solution {
public:
bool isScramble(string &s1, string &s2) {
int m = s1.size(), n = s2.size();
if (m != n)
return false;
vector<vector<vector<bool>>> dp(m, vector<vector<bool>>(m, vector<bool>(m + 1, false)));
for (int i = 0; i < m; i++) {
for (int j = 0; j < m; j++) {
dp[i][j][1] = (s1[i] == s2[j]);
}
}
for (int k = 2; k <= m; k++) {
for (int i = 0; i <= m - k; i++) {
for (int j = 0; j <= m - k; j++) {
for (int w = 1; w < k; w++) {
if (dp[i][j][w] && dp[i + w][j + w][k - w]) {
dp[i][j][k] = true;
break;
}
if (dp[i][j + k - w][w] && dp[i + w][j][k - w]) {
dp[i][j][k] = true;
break;
}
}
}
}
}
return dp[0][0][m];
}
};
