const int N = 40;
class Solution {
public:
// 记忆化搜索存储状态的数组
// -1 表示 false,1 表示 true,0 表示未计算
int memo[N][N][N];
string s1, s2;
bool isSimilar(int i1, int i2, int length){
unordered_map<int, int> freq;
for (int i = i1; i < i1 + length; ++i) {
++freq[s1[i]];
}
for (int i = i2; i < i2 + length; ++i) {
--freq[s2[i]];
}
if (any_of(freq.begin(), freq.end(), [](const auto& entry) {return entry.second != 0;})) {
return false;
}
return true;
}
// 第一个字符串从 i1 开始,第二个字符串从 i2 开始,子串的长度为 length,是否和谐
bool dfs(int i1, int i2, int length){
if (memo[i1][i2][length]) {
return memo[i1][i2][length] == 1;
}
// 判断两个子串是否相等
if (s1.substr(i1, length) == s2.substr(i2, length)) {
memo[i1][i2][length] = 1;
return true;
}
// 判断是否存在字符 c 在两个子串中出现的次数不同
if (!isSimilar(i1, i2, length)) {
memo[i1][i2][length] = -1;
return false;
}
// 枚举分割位置
for (int i = 1; i < length; ++i) {
// 不交换的情况
if (dfs(i1, i2, i) && dfs(i1 + i, i2 + i, length - i)) {
memo[i1][i2][length] = 1;
return true;
}
// 交换的情况
if (dfs(i1, i2 + length - i, i) && dfs(i1 + i, i2, length - i)) {
memo[i1][i2][length] = 1;
return true;
}
}
memo[i1][i2][length] = -1;
return false;
}
bool isScramble(string s1, string s2) {
memset(memo, 0, sizeof(memo));
this->s1 = s1;
this->s2 = s2;
return dfs(0, 0, s1.size());
}
};
讲解的代码,直接用dp
https://www.acwing.com/video/2791/
const int N = 40;
class Solution {
public:
int f[N][N][N];
bool isScramble(string s1, string s2) {
int n = s1.size();
if(s1 == s2) return true;
for(int k = 1; k <= n; k++){
for(int i = 0; i + k -1 < n; i++){
for(int j = 0; j + k - 1 < n; j++){
if(k == 1){
if(s1[i] == s2[j]) f[i][j][k] = true;
}else{
for(int u = 1; u < k; u++){
if(f[i][j][u] && f[i+u][j+u][k-u] || f[i][j+k-u][u] && f[i+u][j][k-u]){
f[i][j][k] = true;
break;
}
}
}
}
}
}
return f[0][0][n];
}
};