#87 - Scramble String - LeetCode JavaScript Solutions

#87 - Scramble String

Problem Description

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

If the length of the string is 1, stop.
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.

Solution

/**
 * @param {string} s1
 * @param {string} s2
 * @return {boolean}
 */
var isScramble = function(s1, s2) {
  const n = s1.length;
  const dp = new Array(n).fill().map(() => new Array(n).fill().map(() => new Array(n).fill(null)));

  function dfs(i1, j1, i2) {
    if (dp[i1][j1][i2] !== null) {
      return dp[i1][j1][i2];
    }
    if (i1 == j1) {
      return dp[i1][j1][i2] = s1[i1] === s2[i2];
    }

    const j2 = j1 - i1 + i2;
    let result = false;
    for (let i = i1; i < j1; i++) {
      result = result || (dfs(i1, i, i2) && dfs(i + 1, j1, i2 + i - i1 + 1))
        || (dfs(i1, i, j2 - i + i1) && dfs(i + 1, j1, i2));
    }

    return dp[i1][j1][i2] = result;
  }

  return dfs(0, n - 1, 0);
};