Skip to content

87. Scramble String

  • Time: $O(n^4)$
  • Space: $O(n^2)$
 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
34
class Solution {
 public:
  bool isScramble(string s1, string s2) {
    if (s1 == s2)
      return true;
    const string hashKey = s1 + '+' + s2;
    if (const auto it = mem.find(hashKey); it != mem.cend())
      return it->second;

    vector<int> count(128);

    for (int i = 0; i < s1.length(); ++i) {
      ++count[s1[i]];
      --count[s2[i]];
    }

    if (ranges::any_of(count, [](int c) { return c != 0; }))
      return mem[hashKey] = false;

    for (int i = 1; i < s1.length(); ++i) {
      if (isScramble(s1.substr(0, i), s2.substr(0, i)) &&
          isScramble(s1.substr(i), s2.substr(i)))
        return mem[hashKey] = true;
      if (isScramble(s1.substr(0, i), s2.substr(s2.length() - i)) &&
          isScramble(s1.substr(i), s2.substr(0, s2.length() - i)))
        return mem[hashKey] = true;
    }

    return mem[hashKey] = false;
  }

 private:
  unordered_map<string, bool> mem;
};

 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
34
35
36
37
38
39
40
class Solution {
  public boolean isScramble(String s1, String s2) {
    if (s1.equals(s2))
      return true;
    final String hashKey = s1 + "+" + s2;
    if (mem.containsKey(hashKey))
      return mem.get(hashKey);

    int[] count = new int[128];

    for (int i = 0; i < s1.length(); ++i) {
      ++count[s1.charAt(i)];
      --count[s2.charAt(i)];
    }

    for (final int freq : count)
      if (freq != 0) {
        mem.put(hashKey, false);
        return false;
      }

    for (int i = 1; i < s1.length(); ++i) {
      if (isScramble(s1.substring(0, i), s2.substring(0, i)) &&
          isScramble(s1.substring(i), s2.substring(i))) {
        mem.put(hashKey, true);
        return true;
      }
      if (isScramble(s1.substring(0, i), s2.substring(s2.length() - i)) &&
          isScramble(s1.substring(i), s2.substring(0, s2.length() - i))) {
        mem.put(hashKey, true);
        return true;
      }
    }

    mem.put(hashKey, false);
    return false;
  }

  private Map<String, Boolean> mem = new HashMap<>();
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution:
  @functools.lru_cache(None)
  def isScramble(self, s1: str, s2: str) -> bool:
    if s1 == s2:
      return True
    if collections.Counter(s1) != collections.Counter(s2):
      return False

    for i in range(1, len(s1)):
      if self.isScramble(s1[:i], s2[:i]) and self.isScramble(s1[i:], s2[i:]):
        return True
      if (self.isScramble(s1[:i], s2[len(s2) - i:]) and
              self.isScramble(s1[i:], s2[: len(s2) - i])):
        return True

    return False