全部回复 共 1 条

1. 许诺 #1 楼主 · 2025-02-22

   #include <iostream>
   #include <string>
   #include <vector>
   

   using namespace std;

   bool isScramble(string s, string t) {

   int n = s.size();
   if (n != t.size()) return false;
   if (s == t) return true;
   
   // 检查字符频率是否相同
   int count[26] = {0};
   for (int i = 0; i < n; i++) {
       count[s[i] - 'a']++;
       count[t[i] - 'a']--;
   }
   for (int i = 0; i < 26; i++) {
       if (count[i] != 0) return false;
   }
   
   // 初始化动态规划数组
   vector<vector<vector<bool>>> dp(n, vector<vector<bool>>(n, vector<bool>(n + 1, false)));
   
   // 填充长度为1的情况
   for (int i = 0; i < n; i++) {
       for (int j = 0; j < n; j++) {
           dp[i][j][1] = (s[i] == t[j]);
       }
   }
   
   // 处理长度从2到n的情况
   for (int len = 2; len <= n; len++) {
       for (int i = 0; i <= n - len; i++) { // s的起始位置i
           for (int j = 0; j <= n - len; j++) { // t的起始位置j
               // 遍历所有可能的分割点k
               for (int k = 1; k < len; k++) {
                   // 情况一：不交换，检查左左和右右是否匹配
                   if (dp[i][j][k] && dp[i + k][j + k][len - k]) {
                       dp[i][j][len] = true;
                       break;
                   }
                   // 情况二：交换，检查左右和右左是否匹配
                   if (dp[i][j + (len - k)][k] && dp[i + k][j][len - k]) {
                       dp[i][j][len] = true;
                       break;
                   }
               }
           }
       }
   }
   
   return dp[0][0][n];
   

   }

   int main() {

   string s, t;
   cin >> s >> t;
   cout << (isScramble(s, t) ? "true" : "false");
   return 0;
   

   } 咳咳咳，还是给吧