Algo | LeetCode 87 Scramble String

Description

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":

1
2
3
4
5
6
7
    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".

1
2
3
4
5
6
7
    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".

1
2
3
4
5
6
7
    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:

1
2
Input: s1 = "great", s2 = "rgeat"
Output: true

Example 2:

1
2
Input: s1 = "abcde", s2 = "caebd"
Output: false

Approach #1 Recursion

Intuition

给定字符串$S$和$T$,判断两者是否满足混淆的条件。而混淆的条件是将字符串以树的形式交换兄弟节点。

实际上这道题是一道递归的题目,我们可以发现混淆是将字符串分成两段,然后交换这两段,构成一个新的字符串。那么对于任意一个字符串,我们有如下的混淆方案。

1
2
3
4
5
S -> T

1. S == T
2. S_left -> T.left, S_right -> T.right
3. S_left -> T.right, S_right -> T.left

可以观察到->混淆操作实际上就是一个递归的过程,条件1是递归基,条件2、3是递归本体。我们每一层递归都将字符串分割成左右节点,然后判断分割后的$S$能否通过混淆操作得到$T$。当$S=T$时,我们就认定混淆操作能达到目的。

但是,我们并不能确定分割字符串的位置,因为在任何位置都可以将字符串分割成左右节点。因此,我们要遍历递归,左右字符串的长度是不确定的,所有长度值都要判断是否能满足混淆条件。

因为每个长度都要判断,那么如果一直递归到最终$S$的长度为1,将会开销很大。为了将某些可以提前判断为不满足混淆条件的分支剪掉,我们需要每次递归判断一下$S$和$T$包含的字符是否相同。如果不相同,那肯定是无法通过混淆操作使$S$变成$T$的。

最终,只要简单处理一下每次递归的结果,就可以知道原本的字符串$S$、$T$是否满足条件了。

Algorithm

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
bool isScramble(string s1, string s2) {
if (s1 == s2) {
return true;
}
int count[26] = {0};
for (int i = 0; i < s1.length(); i++) {
count[s1[i]-'a']++;
}
for (int i = 0; i < s2.length(); i++) {
count[s2[i]-'a']--;
if (count[s2[i]-'a'] < 0) {
return false;
}
}
for (int i = 1; i < s1.length(); i++) {
if (isScramble(s1.substr(0, i), s2.substr(0, i)) && isScramble(s1.substr(i), s2.substr(i))) {
return true;
}
if (isScramble(s1.substr(0, i), s2.substr(s2.length()-i)) && isScramble(s1.substr(i), s2.substr(0, s2.length()-i))) {
return true;
}
}
return false;
}
};

Finally

这是一道简单的递归题目,需要留意的是可能漏掉任意长度都需要递归的情况。

土豪与Zhenly通道
0%