LeetCode 0087 - Scramble String
# Hints
- 区间DP
# 题面
Difficulty | Time Complexity Limit | Extra-Memory Complexity Limit |
---|---|---|
Hard |
Given a string , 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 and of the same length, determine if is a scrambled string of .
Example 1:
Input: s1 = "great", s2 = "rgeat"
Output: true
Example 2:
Input: s1 = "abcde", s2 = "caebd"
Output: false
# 题意
定义字符串 的扰乱如下:
首先把 构造成二叉树的结构,树上的每个节点为 的某个子串,且节点 所表示的子串为 的子节点 和 所表示的子串左右相连的结果,如此递归构造直至子串长度为 ,即作为叶子节点。显然符合条件的树存在多种,如题目样例所示。
可以任意多次交换 的树上的某个非叶子节点的两个子树。最后从左到右读取叶子节点,得到的字符串即为 的扰乱。显然符合条件的扰乱存在多种。
给定两个长度相同的字符串 和 ,判断 是否为 的任意一种可能的扰乱。
# 题解
考虑动态规划,设 表示 是否为 的某种扰乱。
状态转移方程:
$\begin{cases} dp[i][j][1] &= (s_1[i] == s_2[j])\ dp[i][j][len] &= (dp[i][j][k]\ &\ dp[i + k][j + k][len - k]) \mid\ &\ \ \ \ (dp[i][j + len - k][k]\ &\ dp[i + k][j][len - k]) \end{cases}$
我们考虑枚举当前子串的划分位置 ,那么 和 相匹配有两种可能的情况,即是否交换左右子树。
如果不交换子树,则 与 相匹配,而 与 相匹配;
如果交换子树,则 与 相匹配,而 与 相匹配;
由此可得状态转移方程。
最终的答案即为 。时间复杂度为 。
# AC代码
class Solution {
public:
bool isScramble(const string & s1, const string & s2) {
// 初始化
int n = s1.length();
bool dp[n][n][n + 1];
memset(dp, false, sizeof(dp));
// 递推
for (int i = 0; i < n; i ++) for (int j = 0; j < n; j ++) {
dp[i][j][1] = (s1[i] == s2[j]);
}
for (int len = 2; len <= n; len ++) {
for (int i = 0; i + len - 1 < n; i ++) for (int j = 0; j + len - 1 < n; j ++) {
for (int k = 1; k < len; k ++) {
dp[i][j][len] |= (dp[i][j][k] && dp[i + k][j + k][len - k]);
dp[i][j][len] |= (dp[i][j + len - k][k] && dp[i + k][j][len - k]);
}
}
}
// 返回
return dp[0][0][n];
}
};
- 01
- Reading Papers - Kernel Concurrency06-01
- 02
- Linux Kernel - Source Code Overview05-01
- 03
- Linux Kernel - Per-CPU Storage05-01