LeetCode 87.Scramble String

代码查看“原文阅读”

Description

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 / \ 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 and swap its two children, it produces a scrambled string .

rgeat / \ rg eat / \ / \r g e at / \ a t

We say that is a scrambled string of .

Similarly, if we continue to swap the children of nodes and , it produces a scrambled string .

rgtae / \ rg tae / \ / \r g ta e / \ t a

We say that is a scrambled string of .

Given two stringss1ands2of the same length, determine ifs2is a scrambled string ofs1.

Example 1:

Input:

s1 = "great", s2 = "rgeat"

Output:

true

Example 2:

Input:

s1 = "abcde", s2 = "caebd"

Output:

falseSolutions

iff 和可以分为两部分，这两部分分别符合Scramble String。

即存在，使得或者

对应下面两种匹配方式：

下面是两种解法：

Top-down

这里使用了prefixSum和suffixSum来进行剪枝

如果则s1[:k], s2[:k]的和一定相等，所以先判断prefixSum1和prefixSum2

如果则s1[:k], s2[N-k:]的和一定相等，所以先判断prefixSum1和suffixSum2

Python:

Java:

Bottom-up

表示

Python:

Java: