题目链接：Scramble String
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.
这道题的要求是判断两个字符串是否是Scramble String。
如果两个字符串是Scramble String，则其长度必然相等。而且，在某位置切开s1，则s1左侧与s2左侧相同数量的子串为Scramble String，并且s1右侧与s2右侧相同数量的子串为Scramble String；或者s1左侧与s2右侧相同数量的子串为Scramble String，并且s1右侧与s2左侧相同数量的子串为Scramble String。
-
递归处理
思路有了，就可以通过递归调用遍历每组分割点了。其中a1和b1分别表示s1中以a1开始b1结束的子串，a2和b2分别表示s2中以a2开始b2结束的子串。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
bool isScramble(string s1, int a1, int b1, string s2, int a2, int b2)
{
if(b1 - a1 != b2 - a2)
return false;
if(a1 == b1)
return s1[a1] == s2[a2];
for(int i = a1; i < b1; ++ i)
{
if(isScramble(s1, a1, i, s2, a2, a2 + i - a1) &&
isScramble(s1, i + 1, b1, s2, b2 - (b1 - i - 1), b2))
return true;
if(isScramble(s1, a1, i, s2, b2 - (i - a1), b2) &&
isScramble(s1, i + 1, b1, s2, a2, a2 + b1 - i - 1))
return true;
}
return false;
}
遗憾的是，超时。。。仔细想一下，还可以进行剪枝：如果s1和s2的子串中的字符不相同，则其必然不是Scramble String。
顺利AC。
时间复杂度：O(???)
空间复杂度：O(1)
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
28
29
30
31
32
33
34
35
36
37
38
class Solution
{
public:
bool isScramble(string s1, string s2)
{
return isScramble(s1, 0, s1.size() - 1, s2, 0, s2.size() - 1);
}
private:
bool isScramble(string s1, int a1, int b1, string s2, int a2, int b2)
{
if(b1 - a1 != b2 - a2)
return false;
if(a1 == b1)
return s1[a1] == s2[a2];
// 剪枝，如果子串中的字符不同，则必然不是Scramble String，不用再进行分割处理了
int cnt[256] = {0};
for(int i = a1; i <= b1; ++ i)
++ cnt[s1[i]];
for(int i = a2; i <= b2; ++ i)
-- cnt[s2[i]];
for(int i = 0; i < 256 ;++ i)
if(cnt[i] != 0)
return false;
for(int i = a1; i < b1; ++ i)
{
if(isScramble(s1, a1, i, s2, a2, a2 + i - a1) &&
isScramble(s1, i + 1, b1, s2, b2 - (b1 - i - 1), b2))
return true;
if(isScramble(s1, a1, i, s2, b2 - (i - a1), b2) &&
isScramble(s1, i + 1, b1, s2, a2, a2 + b1 - i - 1))
return true;
}
return false;
}
};
-
动态规划
维护变量dp[i][j][len]，其中i是s1的起始字符，j是s2的起始字符，而n是当前的字符串长度，表示的是以i和j分别为s1和s2起点的长度为len的字符串是不是互为Scramble String。
| 递推公式也是前面的思路：dp[i][j][len] | = (dp[i][j][k]&&dp[i+k][j+k][len-k] | dp[i][j+len-k][k]&&dp[i+k][j][len-k])。 |
参考自这里。
时间复杂度：O(???)
空间复杂度：O(1)
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
class Solution
{
public:
bool isScramble(string s1, string s2)
{
if(s1.size() == 0)
return true;
// dp[i][j][len]表示的是以i和j分别为s1和s2起点的长度为len的字符串是不是互为Scramble String
vector<vector<vector<bool> > > dp(s1.size(),
vector<vector<bool> >(s2.size(),
vector<bool>(s1.size() + 1, false)));
for(int i = 0; i < s1.size(); ++ i)
for(int j = 0; j < s2.size(); ++ j)
dp[i][j][1] = s1[i] == s2[j];
for(int len = 2; len <= s1.size(); ++ len)
for(int i = 0; i < s1.size() - len + 1; ++ i)
for(int j = 0; j < s2.size() - len + 1; ++ j)
for(int k = 1; k < len; ++ k)
dp[i][j][len] = dp[i][j][len] ||
dp[i][j][k] && dp[i + k][j + k][len - k] ||
dp[i][j + len - k][k] && dp[i + k][j][len - k];
return dp[0][0][s1.size()];
}
};