题目：87. 扰乱字符串 - 力扣（LeetCode）

dfs+状态记录。

• dfs：以两个字符串 [a1,a2,a3,a4] 和 [b1,b2,b3,b4]为例，可以往下搜以下几种情况，一种情况为true就能返回true
  • F([a1],[b1]) && F([a2,a3,a4],[b2,b3,b4])
  • F([a1],[b4]) && F([a2,a3,a4],[b1,b2,b3])
  • F([a1,a2],[b1,b2]) && F([a3,a4],[b3,b4])
  • F([a1,a2],[b3,b4]) && F([a3,a4],[b1,b2])
  • F([a1,a2,a3],[b1,b2,b3]) && F([a4],[b4])
  • F([a1,a2,a3],[b2,b3,a4]) && F([a4],[b1])
• 状态记录：记录两个字符串a和b的起始位置和长度，可以用一个三维数组表示 f[ia][ib][length] ，看数据规模只有 30，嫌麻烦直接用了一维数组 f[ia * 10000 + ib * 100 + length]

  class Solution {
  public:bool F(const char* a, const char* b, int ia, int ib, int len, uint8_t* f) {if (len == 1 && a[ia] == b[ib]) {return true;}int idx = ia * 10000 + ib * 100 + len;if (f[idx]) {return f[idx] == 1;}f[idx] = 1;for (int i = 0; i < len; i++) {if (a[ia + i] != b[ib + i]) {f[idx] = 2;break;}}if (f[idx] == 1) {return true;}for (int i = 1; i < len; i++) {if (F(a, b, ia, ib, i, f) && F(a, b, ia + i, ib + i, len - i, f)) {f[idx] = 1;break;}if (F(a, b, ia, ib + len - i, i, f) && F(a, b, ia + i, ib, len - i, f)) {f[idx] = 1;break;}}return f[idx] == 1;}bool isScramble(string s1, string s2) {const char* a = s1.c_str();const char* b = s2.c_str();int n = (int) s1.length();uint8_t* f = new uint8_t[400000];memset(f, 0, 400000);return F(a, b, 0, 0, n, f);}
  };