当前位置:网站首页>旋变串判断
旋变串判断
2022-07-04 20:34:00 【N. LAWLIET】
问题
给定两个字符串,str1和str2判断str2是否是str1的旋变串。
旋变串定义
示例:
str1 = abcd str2 = acdb
return false;
思想:
分段来看是否护卫旋变串,dp表加上递归。Dp表存0,1,-1值相等为一,不等为-1.
分成俩种四段来比较,顺位的俩段,和逆位置俩段。
代码
public class Code03_ScrambleString {
public static boolean isScramble0(String str1,String str2) {
if((str1==null&&str2!=null)||(str1!=null&&str2==null)) {
return false;
}
if(str1==null&&str2==null) {
return true;
}
if(str1.length()!=str2.length()) {
return false;
}
char[] s1 = str1.toCharArray();
char[] s2 = str2.toCharArray();
return process(s1,0,s1.length,s2,0,s2.length);
}
private static boolean process(char[] s1, int L1, int R1, char[] s2, int L2, int R2) {
if(L1 == R1) {
return s1[L1] == s2[L2];
}
for(int end = L1;end<R1;end++) {
//正位比较
boolean p1 = process(s1, L1, end, s2, L2, L2+end-L1)&&process(s1, end+1, R1, s2, L2+end-L1+1, R2);
//逆位比较
boolean p2 = process(s1, L1, end, s2, R2-(L2+end-L1)+1, R2)&&process(s1, end+1, R1, s2, L2,R2-(L2+end-L1));
if(p1||p2) {
return true;
}
}
return false;
}
public static boolean isScramble1(String str1,String str2) {
if((str1==null&&str2!=null)||(str1!=null&&str2==null)) {
return false;
}
if(str1==null&&str2==null) {
return true;
}
if(str1.length()!=str2.length()) {
return false;
}
char[] s1 = str1.toCharArray();
char[] s2 = str2.toCharArray();
int N = s1.length;
int[][][] dp = new int[N][N][N+1];
return process1(s1,s2,0,0,N,dp);
}
public static boolean process1(char[] s1,char[] s2,int L1,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 = s1[L1] == s2[L2];
}
for(int end = L1;end<size;end++) {
if((process1(s1,s2, L1+end,L2+end,size-end,dp)&&process1(s1,s2,L1,L2,end,dp))||
(process1(s1, s2, L1, L2+size-end, end, dp)&&process1(s1, s2, L1+end, L2, size-end, dp))) {
ans = true;
break;
}
}
dp[L1][L2][size] = ans?1:-1;
return ans;
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
while(scanner.hasNext()) {
String str1 = scanner.nextLine();
String str2 = scanner.nextLine();
boolean ans = isScramble1(str1, str2);
System.out.println(ans);
}
}
}
边栏推荐
猜你喜欢
Y56. Chapter III kubernetes from entry to proficiency -- business image version upgrade and rollback (29)
【1200. 最小絕對差】
Gobang go to work fishing tools can be LAN / man-machine
Jerry's ad series MIDI function description [chapter]
网络命名空间
解析steam教育中蕴含的众创空间
Golang中UTF编码和字符集
华为ensp模拟器 DNS服务器的配置
UTF encoding and character set in golang
At the right time, the Guangzhou station of the city chain science and Technology Strategy Summit was successfully held
随机推荐
杰理之AD 系列 MIDI 功能说明【篇】
2021 CCPC 哈尔滨 I. Power and Zero(二进制 + 思维)
OMS系统实战的三两事
Difference between ApplicationContext and beanfactory (MS)
What are the functional modules of RFID warehouse management system solution
FastDfs的快速入门,三分钟带你上传下载文件到云服务器
杰理之AD 系列 MIDI 功能说明【篇】
杰理之AD 系列 MIDI 功能说明【篇】
【微信小程序】协同工作与发布
Huawei ENSP simulator configures DHCP for router
Huawei ENSP simulator layer 3 switch
UTF encoding and character set in golang
colResizable.js自动调整表格宽度插件
Golang中UTF编码和字符集
redis发布订阅的使用
实战模拟│JWT 登录认证
numpy vstack 和 column_stack
Y56. Chapter III kubernetes from entry to proficiency -- business image version upgrade and rollback (29)
创客思维在高等教育中的启迪作用
Day24: file system