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

Below is one possible representation ofs1 = "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 stringss1ands2of the same length, determine ifs2is a scrambled string ofs1.

Have you met this question in a real interview?

Yes

Example

Challenge

O(n3) time

line 23 ++k not ++i , i undefined variable name

dp
line 24 k starting from 2 not 1 , otherwise will lead to error

line 29, 30 cannot use ||= there is no such operator

better initilize 27

line 25 26 , i j range less than len - k , otherwise may lead to wrong result

line 16 using const to have array like 17

class Solution {

public:

/\*\*

 \* @param s1 A string

 \* @param s2 Another string

 \* @return whether s2 is a scrambled string of s1

 \*/

bool isScramble\(string& s1, string& s2\) {

    // Write your code here

    if \(s1.size\(\) != s2.size\(\)\) {

        return false;

    }

    if \(s1.empty\(\)\) {

        return true;

    }

    int len = s1.size\(\);

    bool dp\[len + 1\]\[len\]\[len\];

    for \(int i = 0; i < len; ++i\) {

        for \(int j = 0; j < len; ++j\) {

            dp\[1\]\[i\]\[j\] = s1\[i\] == s2\[j\];

        }

    }



    for \(int k = 2; k <= len; ++k\) {

        for \(int i = 0; i <= len - k; ++i\) {

            for \(int j = 0; j <= len - k; ++j\) {

                dp\[k\]\[i\]\[j\] = false;

                for \(int m = 1; m < k; ++m\) {

                    dp\[k\]\[i\]\[j\] = dp\[k\]\[i\]\[j\] \|\| \(dp\[m\]\[i\]\[j\] && dp\[k-m\]\[i+m\]\[j+m\]\);

                    dp\[k\]\[i\]\[j\] = dp\[k\]\[i\]\[j\] \|\| \(dp\[m\]\[i\]\[j+k-m\] && dp\[k-m\]\[i+m\]\[j\]\);

                }

            }

        }

    }

    return dp\[len\]\[0\]\[0\];

}

};

results matching ""

    No results matching ""