文章目录
前言
暴力递归
二、记忆化搜索
前言
使用下面描述的算法可以扰乱字符串 s 得到字符串 t ：
如果字符串的长度为 1 ，算法停止
如果字符串的长度 > 1 ，执行下述步骤：
在一个随机下标处将字符串分割成两个非空的子字符串。即，如果已知字符串 s ，则可以将其分成两个子字符串 x 和 y ，且满足 s = x + y 。
随机 决定是要「交换两个子字符串」还是要「保持这两个子字符串的顺序不变」。即，在执行这一步骤之后，s 可能是 s = x + y 或者 s = y + x 。
在 x 和 y 这两个子字符串上继续从步骤 1 开始递归执行此算法。
给你两个 长度相等 的字符串 s1 和 s2，判断 s2 是否是 s1 的扰乱字符串。如果是，返回 true ；否则，返回 false 。
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/scramble-string
暴力递归
样本对应模型
按第一刀的情况来分
定义函数f(s1,L1,R1, s2,L2,R2):
str1的L1-R1,对str2 L2-R2等长，看str1的L1~R1,对str2 L2~R2这一段是不是玄变字符串
Interlaken Protocol白皮书(中文)
0星
超过10%的资源
851KB
下载
base case
当你L1到R1上只有一个字符，
如果str1[L1]==str2[L2],返回true
普遍情况
枚举的方式是str1第一刀切哪儿了
1)第一刀0-0, 1-9
两种情况
1.两个字符串一一对应
2.str1前部分对于str2后部分,str1后部分对应str2前部分
即字符进行了变换
2)0-1,2-9
…
9)0-8,9-9
public static boolean isScramble(String s1, String s2) {
if ((s1 == null && s2 != null) || (s1 != null && s2 == null)) {
return false;
}
if (s1 == null && s2 == null) {
return true;
}
if (s1.equals(s2)) {
return true;
}
char[] str1 = s1.toCharArray();
char[] str2 = s2.toCharArray();
if (!sameTypeSameNumber(str1, str2)) {
return false;
}
return process0(str1, 0, str1.length - 1, str2, 0, str2.length - 1);
}
// str1[L1...R1] str2[L2...R2] 是否互为玄变串
// 一定保证这两段是等长的！
public static boolean process(char[] str1, int L1, int R1, char[] str2, int L2, int R2) {
if (L1 == R1) {
return str1[L1] == str2[L2];
}
for (int leftEnd = L1; leftEnd < R1; leftEnd++) {
boolean p1 = process0(str1, L1, leftEnd, str2, L2, L2 + leftEnd - L1)
&& process0(str1, leftEnd + 1, R1, str2, L2 + leftEnd - L1 + 1, R2);
boolean p2 = process0(str1, L1, leftEnd, str2, R2 - (leftEnd - L1), R2)
&& process0(str1, leftEnd + 1, R1, str2, L2, R2 - (leftEnd - L1) - 1);
if (p1 || p2) {
return true;
}
}
return false;
}
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
二、记忆化搜索
如果我们使用四维表记录的话,那就太浪费空间了
我们可以减少一维,使用三维表
递归参数设置为
process(char[] str1,int L1,char[] str2,int L2,int size,int[][][] dp)
1
用size可以推出R1和R2
这样就可以节省空间了
class Solution {
public boolean isScramble(String s1, String s2) {
if ((s1 == null && s2 != null) || (s1 != null && s2 == null)) {
return false;
}
if (s1 == null && s2 == null) {
return true;
}
if (s1.equals(s2)) {
return true;
}
char[] str1=s1.toCharArray();
char[] str2=s2.toCharArray();
int size=str1.length;
int[][][] dp=new int[size][size][size+1];
return process(str1,0,str2,0,size,dp);
}
public boolean process(char[] str1,int L1,char[] str2,int L2,int size,int[][][] dp){
if(dp[L1][L2][size]!=0){
return dp[L1][L2][size]==1;
}
boolean ans = false;
if(size==1){
ans=str1[L1]==str2[L2];
}else{
for(int leftPart=1;leftPart<size;leftPart++){
boolean p1=process(str1,L1,str2,L2,leftPart,dp)
&&process(str1,L1+leftPart,str2,L2+leftPart,size-leftPart,dp);
boolean p2=process(str1,L1,str2,L2+size-leftPart,leftPart,dp)&&
process(str1,L1+leftPart,str2,L2,size-leftPart,dp);
if(p1||p2){
ans=true;
break;
}
}
}
dp[L1][L2][size]=ans?1:-1;
return ans;
}
}
