【题目描述】
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.
给定一个字符串 S1，将其递归地分割成两个非空子字符串,从而将其表示为二叉树。
下面是s1 = "great"的一个可能表达：
great
/ \
gr eat
/ \ / \
g r e at
/ \
a t
在攀爬字符串的过程中，我们可以选择其中任意一个非叶节点，然后交换该节点的两个儿子。
例如，我们选择了 "gr" 节点，并将该节点的两个儿子进行交换，从而产生了攀爬字符串 "rgeat"。
rgeat
/ \
rg eat
/ \ / \
r g e at
/ \
a t
我们认为， "rgeat" 是 "great" 的一个攀爬字符串.
类似地，如果我们继续将其节点 "eat" 和 "at" 进行交换，就会产生新的攀爬字符串 "rgtae"。
rgtae
/ \
rg tae
/ \ / \
r g ta e
/ \
t a
同样地，"rgtae" 也是 "great"的一个攀爬字符串。
给定两个相同长度的字符串s1 和 s2，判定 s2 是否为 s1 的攀爬字符串。
【题目链接】
www.lintcode.com/en/problem/scramble-string/
【题目解析】
这道题用二维数组来存储中间结果不够用了，需要一个三维数组 dp[i][j][len]，表示从s1的第i个字符开始长度为len的子串，和从s2的第j个字符开始长度为len的子串，是否互为scramble。
初始化为dp[i][j][1] = s1.charAt(i) == s2.charAt(j)，即长度为1的子串是否互为scramble。
三维数组就要三层循环，最终结果为dp[0][0][s1.length()]，即从s1的第0个字符开始长度为s1.length()的子串，即s1本身和s2本身是否互为scramble。
要判断dp[i][j][len]的值，就要把s1从i开始长度为len的串分别从k=1, 2 ... len-1处切开，判断切成的两半和s2同样切成的两半是否互为scramble，只要有一种切法满足条件，那么dp[i][j][len]就为true，否则为false。
【参考答案】
网友评论