87. Scramble String

Difficulty:
Related Topics:
Similar Questions:

    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

    /**
     * @param {string} s1
     * @param {string} s2
     * @return {boolean}
     */
    var isScramble = function(s1, s2) {
      return helper({}, s1, s2);
    };
    
    var helper = function (dp, s1, s2) {
      var map = {};
    
      if (dp[s1 + s2] !== undefined) return dp[s1 + s2];
      if (s1 === s2) return true;
    
      for (var j = 0; j < s1.length; j++) {
        if (map[s1[j]] === undefined) map[s1[j]] = 0;
        if (map[s2[j]] === undefined) map[s2[j]] = 0;
        map[s1[j]]++;
        map[s2[j]]--;
      }
    
      for (var key in map) {
        if (map[key] !== 0) {
          dp[s1 + s2] = false;
          return false;
        }
      }
    
      for (var i = 1; i < s1.length; i++) {
        if ((helper(dp, s1.substr(0, i), s2.substr(0, i))
             && helper(dp, s1.substr(i), s2.substr(i))) ||
            (helper(dp, s1.substr(0, i), s2.substr(s2.length - i))
             && helper(dp, s1.substr(i), s2.substr(0, s2.length - i)))) {
          dp[s1 + s2] = true;
          return true;
        }
      }
    
      dp[s1 + s2] = false;
      return false;
    };
    

    Explain:

    nope.

    Complexity: