Leetcode 87: Scramble String

https://leetcode.com/problems/scramble-string/

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.

 

Code

class Solution(object):
    def isScramble(self, s1, s2):
        """
        :type s1: str
        :type s2: str
        :rtype: bool
        """
        if len(s1) != len(s2):
            return False
        elif not s1:
            return True
        
        n = len(s1)
        res = [[[False for _ in xrange(n)] for _ in xrange(n)] for _ in xrange(n+1)]  # the size of the first dim is n+1
                                                                                      # easy for indexing
        for j in xrange(n):
            for m in xrange(n):
                res[1][j][m] = (s1[j] == s2[m])
            
        for i in xrange(2, n+1):
            for j in xrange(n-i+1):
                for m in xrange(n-i+1):
                    for k in xrange(1,i):
                        res[i][j][m] |= (res[k][j][m] and res[i-k][j+k][m+k]) \
                                        or (res[k][j][m+i-k] and res[i-k][j+k][m])
                        
        return res[n][0][0]

 

Idea

See here: http://tianmaying.com/tutorial/LC87

One note is that we put for i in xrange(2, n+1)  at the outmost loop (line 20), where `i` is the length of the two substrings, `s1[j:j+i] and s2[m:m+i]`, under comparison. When we calculate `res[i][j][m]`, we always need some `res[k’][j’][m’]` where `k’ < i`. Therefore, we need to calculate `res` in ascending order of `i`, the first dimension of `res`.