代码查看“原文阅读”
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:
领取专属 10元无门槛券
私享最新 技术干货