Scramble String

Question

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.

Thoughts

递归

s2[0...j]是否可以由s1[0...j]转换 isScramble(s2[0...j], s1[0...j])，可以分解成 i 个子问题：

( isScramble(s2[0...k], s1[0...k]) &&  isScramble(s2[k+1...j], s1[k+1...j]) ) 
|| 
( isScramble(s2[0...k], s1[j-k...j]) &&  isScramble(s2[k+1...j], s1[0...j-k-1]) )

，（k = 0,1,2 ... j-1，k相当于字符串的分割点)

DP

递归中有很多重复计算的问题，运用dp来免除重复计算，基本的思路是一样的

scramble string

Solution

class Solution:
    # @param {string} s1 A string
    # @param {string} s2 Another string
    # @return {boolean} whether s2 is a scrambled string of s1
    def isScramble(self, s1, s2):
        # Write your code here
        if len(s1) != len(s2):
            return False

        length = len(s1)
        dp = [[[False for i in range(length)] for j in range(length)] for k in range(length + 1)]

        for i in range(length):
            for j in range(length):
                if s1[i] == s2[j]:
                    dp[1][i][j] = True

        for k in range(2, length + 1):
            for i in  range(length + 1 - k):
                for j in range(length + 1 - k):
                    for div in range(1, k):
                        if dp[k][j][j] == True:
                            break
                        left = dp[div][i][j] and dp[k-div][i+div][j+div]
                        right = dp[div][i][j+k-div] and dp[k-div][i+div][j]
                        dp[k][i][j] =  left or right

        return dp[length][0][0]