1
impl Solution {
2
  pub fn is_scramble(s1: String, s2: String) -> bool {
3
    let n = s1.len();
4
    let (s1, s2) = (s1.as_bytes(), s2.as_bytes());
5
    let mut dp = vec![vec![vec![false; n]; n]; n + 1];
6
    for i in 0..n {
7
      for j in 0..n {
8
        dp[1][i][j] = s1[i] == s2[j];
9
      }
10
    }
11
    for len in 2..=n {
12
      for i in 0..(n + 1 - len) {
13
        for j in 0..(n + 1 - len) {
14
          let mut is_scrambled = dp[len][i][j];
15
          for new_len in 1..len {
16
            let dp1 = &dp[new_len][i];
17
            let dp2 = &dp[len - new_len][i + new_len];
18
            is_scrambled |= dp1[j] && dp2[j + new_len];
19
            is_scrambled |= dp1[j + len - new_len] && dp2[j];
20
          }
21
          dp[len][i][j] = is_scrambled;
22
        }
23
      }
24
    }
25

26
    dp[n][0][0]
27
  }
28
}