# 87. Scramble String

### Leetcode

<https://leetcode.com/problems/scramble-string/>

### 題目

We can scramble a string s to get a string t using the following algorithm:

1. If the length of the string is 1, stop.
2. If the length of the string is > 1, do the following:
   * Split the string into two non-empty substrings at a random index, i.e., if the string is `s`, divide it to `x` and `y` where `s = x + y`.
   * **Randomly** decide to swap the two substrings or to keep them in the same order. i.e., after this step, `s` may become `s = x + y` or `s = y + x`.
   * Apply step 1 recursively on each of the two substrings `x` and `y`.

Given two strings `s1` and `s2` of **the same length**, return `true` if `s2` is a scrambled string of `s1`, otherwise, return `false`.

### 解答 <a href="#ti-jie" id="ti-jie"></a>

* **方法一**

將s1, s2都分別切成前後兩段字串 s1 =>s11, s12; s2 => s21, s22，利用遞歸的方式比較 s11 <=> s21 與 s12 <=> s22 是否都相同，或者，比較 s11 <=> s22 與 s12 <=> s21 兩者是否都相同，只要其中一個判別式為 true，就代表 s1, s2 之間互為 scramble

```
var isScramble = function(s1, s2) {
    // console.log('isScramble', s1, s2);
    if(s1.length !== s2.length) return false;
    if(s1 === s2) return true;
    const s1Sorted = s1.split('').sort().join('');
    const s2Sorted = s2.split('').sort().join('');
    if(s1Sorted !== s2Sorted) return false;

    for(let i=1; i<s1.length; i++) {
      const s11 = s1.substring(0, i);
      const s12 = s1.substring(i);
      // console.log('s1', s1, s11, s12)

      let s21 = s2.substring(0, i);
      let s22 = s2.substring(i);
      // console.log('s2', s2, s21, s22)

      if(isScramble(s11, s21) && isScramble(s12, s22)) return true;
      s21 = s2.substring(s1.length - i);
      s22 = s2.substring(0, s1.length - i);
      // console.log('s2_', s2, s21, s22)

      if(isScramble(s11, s21) && isScramble(s12, s22)) return true;
    }

    return false;
};
```

Time Limit Exceeded

* **方法二**

利用動態規劃 dp，創建一個三維的矩陣記錄每個字串是否為 scramble

ex. s1 = 'gre', s2 = 'rge'

1. 首先在 len 等於 1 時，將一維矩陣的值都求出來

|     |                  r                  |                  g                  |                  e                  |
| :-: | :---------------------------------: | :---------------------------------: | :---------------------------------: |
|  g  |                  x                  | <mark style="color:green;">v</mark> |                  x                  |
|  r  | <mark style="color:green;">v</mark> |                  x                  |                  x                  |
|  e  |                  x                  |                  x                  | <mark style="color:green;">v</mark> |

&#x20; 2\. 接下來可求出 二維矩陣 的值

|     |                  rg                 |  ge |
| :-: | :---------------------------------: | :-: |
|  gr | <mark style="color:green;">v</mark> |  x  |
|  re |                  x                  |  x  |

&#x20; 3\. 最終求出三維矩陣的完全值是否為 scramble

|     |                 rge                 |
| :-: | :---------------------------------: |
| gre | <mark style="color:green;">v</mark> |

例子：

i = 0, j = 0, len = 3, k = 1 的狀況下，判斷 'gre', 'rge' 是否為 scramble ?

```
dp[i][j][k] && dp[i+k][j+k][len-k]
dp[0][0][1] && dp[1][1][2]
false && false
=> 判斷一維矩陣的 g, r && 二維矩陣的 re, gr
```

```
dp[i+k][j][len-k]&& dp[i][j+len-k][k]
dp[1][0][2] && dp[0][2][1]
false && false
=> 判斷二維矩陣的 re, rg && 一維矩陣的 g, e
```

i = 0, j = 0, len = 3, k = 2 的狀況下，判斷 'gre', 'rge' 是否為 scramble ?

```
dp[i][j][k] && dp[i+k][j+k][len-k]
dp[0][0][2] && dp[2][2][1]
true && true
=> 判斷二維矩陣的 gr, rg && 一維矩陣的 e, e
=> 有一條件符合，確定是 scramble!
```

```
dp[i+k][j][len-k]&& dp[i][j+len-k][k]
dp[2][0][1] && dp[0][1][2]
false && false
=> 判斷一維矩陣的 e, r && 二維矩陣的 gr, ge
```

```
var isScramble = function(s1, s2) {
  if (s1 === s2) return true;
  if (s1.length !== s2.length) return false;
  const s1Sorted = s1.split('').sort().join('');
  const s2Sorted = s2.split('').sort().join('');
  if (s1Sorted !== s2Sorted) return false;

  const n = s1.length;
  const dp = [];
  // generate init dp
  for(let i=0; i<n; i++) {
    if(!dp[i]) dp[i] = [];
    for(let j=0; j<n; j++) {
      if(!dp[i][j]) dp[i][j] = [];
      for(let k=0; k<n; k++) {
        dp[i][j][k] = false;
      }
    }
  }

  for(let len=1; len<=n; len++) {
    for(let i=0; i<=n-len; i++) {
      for(let j=0; j<=n-len; j++) {
        if(len === 1) {
          // compare for only one char
          dp[i][j][1] = s1[i] === s2[j]; 
        } else {
          for(let k=1; k<len; k++) {
            if((dp[i][j][k] && dp[i+k][j+k][len-k]) || (dp[i+k][j][len-k]&& dp[i][j+len-k][k])) {
              dp[i][j][len] = true;
            }
          }
        }
      }
    }
  }
  // console.log(dp);
  return dp[0][0][n] || false;
};
```

Runtime: 124 ms, faster than 76.92% of JavaScript online submissions for Scramble String.

Memory Usage: 47.4 MB, less than 53.85% of JavaScript online submissions for Scramble String.

### 測資

```
let s1 = "great", s2 = "rgeat";
s1 = "abb", s2 = "bba";
s1='gre', s2='rge';
s1 = "abcde", s2 = "caebd";
s1="abcdbdacbdac", s2="bdacabcdbdac";

console.log(isScramble(s1, s2));
```

### 參考資料

* <https://www.cnblogs.com/grandyang/p/4318500.html>
