使用下面描述的算法可以扰乱字符串 s 得到字符串 t ：

如果字符串的长度为 1 ，算法停止

如果字符串的长度 > 1 ，执行下述步骤：

  • 在一个随机下标处将字符串分割成两个非空的子字符串。即，如果已知字符串 s ，则可以将其分成两个子字符串 x 和 y ，且满足 s = x + y 。
  • 随机 决定是要「交换两个子字符串」还是要「保持这两个子字符串的顺序不变」。即，在执行这一步骤之后，s 可能是 s = x + y 或者 s = y + x 。
  • 在 x 和 y 这两个子字符串上继续从步骤 1 开始递归执行此算法。

给你两个 长度相等 的字符串 s1 和 s2，判断 s2 是否是 s1 的扰乱字符串。如果是，返回 true ；否则，返回 false 。

思路

  1. 无脑递归尝试求解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
var isScramble = function (s1, s2) {
  if (s1.length !== s2.length) {
    return false
  }
  if (s1 === s2) {
    return true
  }
  if (s1.split('').sort().join('') !== s2.split('').sort().join('')) {
    return false
  }
  for (let i = 1; i < s2.length; ++i) {
    if (isScramble(s1.substring(0, i), s2.substring(0, i)) && isScramble(s1.substring(i), s2.substring(i))) {
      return true
    }
    if (
      isScramble(s1.substring(0, i), s2.substring(s2.length - i)) &&
      isScramble(s1.substring(i), s2.substring(0, s2.length - i))
    ) {
      return true
    }
  }
  return false
}

面对下面测试用例时发生了超时

1
isScramble('eebaacbcbcadaaedceaaacadccd', 'eadcaacabaddaceacbceaabeccd')

改进代码，加入缓存可以避免相同字符串反复计算

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
var isScramble = function (s1, s2) {
  const cache = {}
  const check = (s1, s2) => {
    if (s1.length !== s2.length) {
      return false
    }
    if (s1 === s2) {
      return true
    }
    if (s1.split('').sort().join('') !== s2.split('').sort().join('')) {
      return false
    }
    for (let i = 1; i < s2.length; ++i) {
      const [part11, part12] = [s1.substring(0, i), s1.substring(i)]
      const [part21, part22] = [s2.substring(0, i), s2.substring(i)]
      const [key1121, key1222] = [`${part11},${part21}`, `${part12},${part22}`]
      cache[key1121] = cache[key1121] !== undefined ? cache[key1121] : check(part11, part21)
      cache[key1222] = cache[key1222] !== undefined ? cache[key1222] : check(part12, part22)
      if (cache[key1121] && cache[key1222]) {
        return true
      }
      const [part23, part24] = [s2.substring(s2.length - i), s2.substring(0, s2.length - i)]
      const [key1123, key1224] = [`${part11},${part23}`, `${part12},${part24}`]
      cache[key1123] = cache[key1123] !== undefined ? cache[key1123] : check(part11, part23)
      cache[key1224] = cache[key1224] !== undefined ? cache[key1224] : check(part12, part24)
      if (cache[key1123] && cache[key1224]) {
        return true
      }
    }
    return false
  }
  return check(s1, s2)
}