class Solution {
public:
bool isScramble(string s1, string s2) {
if (s1 == s2) {
return true;
}
if (!is_permutation(s1.begin(), s1.end(), s2.begin())) {
return false;
}
int n = s1.length();
vector<vector<vector<bool>>> dp(n, vector<vector<bool>>(n, vector<bool>(n+1, false)));
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
dp[i][j][1] = (s1[i] == s2[j]);
}
}
for (int length = 2; length <= n; length++) {
for (int i = 0; i <= n-length; i++) {
for (int j = 0; j <= n-length; j++) {
for (int k = 1; k < length; k++) {
if ((dp[i][j][k] && dp[i+k][j+k][length-k]) || (dp[i][j+length-k][k] && dp[i+k][j][length-k])) {
dp[i][j][length] = true;
break;
}
}
}
}
}
return dp[0][0][n];
}
};
leetcode
challenge
Here is the link for the problem:
https://leetcode.com/problems/scramble-string/
Top comments (0)