[LeetCode] 87. Scramble String_hard tag: 区间Dynamic Programming?

偏执的太偏执、 2021-12-11 23:01 152阅读 0赞

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

这个题目我们先判断s1, s2的长度是否相等，然后s1 == s2 否，接着如果s1和s2的所含字符不一样，也肯定不是，接着进入正式的判断搜索，然后分两种情况，s2的后半段有无scramble

1） 无scramble i = \[1, n\]

isScramble(s1\[:i\], s2\[:i\]) and isScramble(s1\[i:\], s2\[i:\])

2) 有scramble

isScramble(s1\[:i\], s2\[-i: \]) and isScramble(s1\[i:\], s2\[: -i\])

Code

class Solution:
        def isScramble(self, s1, s2):
            m, n = len(s1), len(s2)
            if m != n: return False
            if s1 == s2: return True
            if sorted(list(s1)) != sorted(list(s2)):
                return False
            for i in range(1, n):
                if (self.isScramble(s1[:i], s2[:i]) and self.isScramble(s1[i:], s2[i:])) or (self.isScramble(s1[:i], s2[-i:]) and self.isScramble(s1[i:], s2[:-i])):
                    return True
            return False

转载于:https://www.cnblogs.com/Johnsonxiong/p/11136068.html