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.

解答

• 方法一

將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	v	x
r	v	x	x
e	x	x	v

2. 接下來可求出 二維矩陣 的值

	rg	ge
gr	v	x
re	x	x

3. 最終求出三維矩陣的完全值是否為 scramble

	rge
gre	v

例子：

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