当前位置:网站首页>Rotary transformer string judgment
Rotary transformer string judgment
2022-07-04 21:34:00 【N. LAWLIET】
problem
Given two strings ,str1 and str2 Judge str2 Whether it is str1 Rotary transformer string of .
Definition of rotary transformer string
Example :
str1 = abcd str2 = acdb
return false;
thought :
Check whether to protect the spiral transformer string by sections ,dp Table plus recursion .Dp Table storage 0,1,-1 Values equal to one , Don't wait for -1.
Divide into two kinds and four paragraphs to compare , Two paragraphs in sequence , And the reverse position .
Code
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++) {
// Positive comparison
boolean p1 = process(s1, L1, end, s2, L2, L2+end-L1)&&process(s1, end+1, R1, s2, L2+end-L1+1, R2);
// Inverse comparison
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);
}
}
}
边栏推荐
猜你喜欢
Configuration of DNS server of Huawei ENSP simulator
解析steam教育中蕴含的众创空间
admas零件名重复
Jerry's ad series MIDI function description [chapter]
Flutter TextField示例
每日一题-LeetCode1200-最小绝对差-数组-排序
Explication détaillée du mécanisme de distribution des événements d'entrée multimodes
CAD中能显示打印不显示
NetWare r7000 Merlin system virtual memory creation failed, prompting that the USB disk reading and writing speed does not meet the requirements. Solution, is it necessary to create virtual memory??
【活动早知道】LiveVideoStack近期活动一览
随机推荐
插入排序,选择排序,冒泡排序
Huawei simulator ENSP common commands
Methods of improving machine vision system
Gobang go to work fishing tools can be LAN / man-machine
Day24:文件系统
Explication détaillée du mécanisme de distribution des événements d'entrée multimodes
Introduction to pressure measurement of JMeter
Poster cover of glacier
Minidom module writes and parses XML
LambdaQueryWrapper用法
heatmap.js图片热点热力图插件
redis布隆过滤器
华为ensp模拟器 DNS服务器的配置
EhLib 数据库记录的下拉选择
Jerry's ad series MIDI function description [chapter]
【C語言】符號的深度理解
FastDfs的快速入门,三分钟带你上传下载文件到云服务器
Use of redis publish subscription
杰理之AD 系列 MIDI 功能说明【篇】
Jerry's ad series MIDI function description [chapter]