Skip to content

Latest commit

 

History

History
181 lines (139 loc) · 3.57 KB

087. Scramble String.md

File metadata and controls

181 lines (139 loc) · 3.57 KB
Raw
Difficulty Related Topics
Hard

87. Scramble String

Problem:

Given a string s1, we may represent it as a binary tree by partitioning it to two non-empty substrings recursively.

Below is one possible representation of s1 = "great":

    great
   /    \
  gr    eat
 / \    /  \
g   r  e   at
           / \
          a   t

To scramble the string, we may choose any non-leaf node and swap its two children.

For example, if we choose the node "gr" and swap its two children, it produces a scrambled string "rgeat".

    rgeat
   /    \
  rg    eat
 / \    /  \
r   g  e   at
           / \
          a   t

We say that "rgeat" is a scrambled string of "great".

Similarly, if we continue to swap the children of nodes "eat" and "at", it produces a scrambled string "rgtae".

    rgtae
   /    \
  rg    tae
 / \    /  \
r   g  ta  e
       / \
      t   a

We say that "rgtae" is a scrambled string of "great".

Given two strings s1 and s2 of the same length, determine if s2 is a scrambled string of s1.

Example 1:

Input: s1 = "great", s2 = "rgeat"
Output: true

Example 2:

Input: s1 = "abcde", s2 = "caebd"
Output: false

Solution:

Define f(len, i, j) to be whether s2[j...j+len) is a scrambled string of s1[i...i+len).

The method of binary tree generation is not given, so all splitting positions must be considered.

f(1, i, j) = s1[i] == s2[j]
f(len, i, j) = some( f(k, i, j) && f(len-k, i+k, j+k) || f(k, i, j+len-k) && f(len-k, i+k, j) ), 1 < k < len

ONE

Recursive.

/**
 * @param {string} s1
 * @param {string} s2
 * @return {boolean}
 */
var isScramble = function(s1, s2) {
  const len = s1.length
  if (len <= 0 || len !== s2.length) { return false }

  const memo = []
  for (let l = 1; l <= len; l++) {
    memo[l] = []
    for (let i = 0; i < len; i++) {
      memo[l][i] = []
    }
  }

  return _f(s1, s2, memo, len, 0, 0)
};

function _f (s1, s2, memo, l, i, j) {
  if (memo[l][i][j] !== undefined) {
    return memo[l][i][j]
  }

  if (l === 1) {
    return memo[l][i][j] = s1[i] === s2[j]
  }

  for (let k = 1; k < l; k++) {
    const t = _f(s1, s2, memo, k, i, j) && _f(s1, s2, memo, l-k, i+k, j+k) ||
              _f(s1, s2, memo, k, i, j+l-k) && _f(s1, s2, memo, l-k, i+k, j)
    if (t) {
      return memo[l][i][j] = t
    }
  }

  return memo[l][i][j] = false
}

TWO

Bottom-up DP.

/**
 * @param {string} s1
 * @param {string} s2
 * @return {boolean}
 */
var isScramble = function(s1, s2) {
  const len = s1.length
  if (len <= 0 || len !== s2.length) { return false }
  if (len === 1) { return s1 === s2 }

  const dp = [null, []]

  for (let i = 0; i < len; i++) {
    dp[1][i] = []
    for (let j = 0; j < len; j++) {
      dp[1][i][j] = s1[i] === s2[j]
    }
  }

  for (let l = 2; l < len; l++) {
    dp[l] = []
    for (let i = 0; i <= len - l; i++) {
      dp[l][i] = []
      for (let j = 0; j <= len - l; j++) {
        for (let k = 1; k < l; k++) {
          if (dp[l][i][j] = dp[k][i][j] && dp[l-k][i+k][j+k] || dp[k][i][j+l-k] && dp[l-k][i+k][j]) {
            break
          }
        }
      }
    }
  }

  // dp[len][0][0]
  for (let k = 1; k < len; k++) {
    if (dp[k][0][0] && dp[len-k][k][k] || dp[k][0][len-k] && dp[len-k][k][0]) {
      return true
    }
  }

  return false
};

Template generated via Leetmark.