方案一:先建树、后比较
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
/**
* @program: 算法题
* @author: 上杉
* @create: 2021-05-19 20:54
**/
public class Main {
static BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
static String builder;
static String checker;
static int len;
static int index;
static int number = 1;//节点编号
static HashMap<Integer,HashSet<Integer>> map1 = new HashMap<>();
static HashMap<Integer,HashSet<Integer>> map2 = new HashMap<>();
public static void main(String[] args) throws IOException {
//通过一个序列建树,然后检测另一个序列
int T = Integer.parseInt(bf.readLine());
while (T-- > 0){
builder = bf.readLine();checker = bf.readLine();
len = builder.length();
build1(0);
index = 0;number = 1;
build2(0);
String min1 = getMin1(-1,0);
String min2 = getMin2(-1,0);
if (min1.equals(min2)){
System.out.println("same");
}else {
System.out.println("different");
}
index = 0;number = 1;
map1.clear();map2.clear();
}
}
private static String getMin1(int parent,int cur) {
HashSet<Integer> set = map1.get(cur);
if (set.size() == 1 && cur != 0){
return "";
}
String[] str = new String[cur == 0 ? set.size():set.size() - 1];
int i = 0;
for (Integer son : set) {
if (son != parent){
str[i++] = getMin1(cur,son);
}
}
Arrays.sort(str);
StringBuilder sb = new StringBuilder();
for (String s : str) {
sb.append(0);
sb.append(s);
sb.append(1);
}
return sb.toString();
}
private static String getMin2(int parent,int cur) {
HashSet<Integer> set = map2.get(cur);
if (set.size() == 1 && cur != 0){
return "";
}
String[] str = new String[cur == 0 ? set.size():set.size() - 1];
int i = 0;
for (Integer son : set) {
if (son != parent){
str[i++] = getMin2(cur,son);
}
}
Arrays.sort(str);
StringBuilder sb = new StringBuilder();
for (String s : str) {
sb.append(0);
sb.append(s);
sb.append(1);
}
return sb.toString();
}
private static void build2(int parent) {
if (index == len)return;
char c = checker.charAt(index);
if (c == '1'){
index++;
}else {
//有了新节点
int newNum = number++;
HashSet<Integer> set1 = map2.get(parent);
if (set1 == null){
set1 = new HashSet<>();
map2.put(parent,set1);
}
set1.add(newNum);
HashSet<Integer> set2 = new HashSet<>();
set2.add(parent);
map2.put(newNum,set2);
index++;
build2(newNum);
if (index == len)return;
else build2(parent);
}
}
private static void build1(int parent) {
if (index == len)return;
char c = builder.charAt(index);
if (c == '1'){
index++;
}else {
//有了新节点
int newNum = number++;
HashSet<Integer> set1 = map1.get(parent);
if (set1 == null){
set1 = new HashSet<>();
map1.put(parent,set1);
}
set1.add(newNum);
HashSet<Integer> set2 = new HashSet<>();
set2.add(parent);
map1.put(newNum,set2);
index++;
build1(newNum);
if (index == len)return;
else build1(parent);
}
}
}
方案二:直接比较
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
/**
* @program: 算法题
* @author: 上杉
* @create: 2021-05-19 22:01
**/
public class Main {
static int index;
public static void main(String[] args) throws IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(bf.readLine());
while (T-- > 0) {
String str1 = "0"+bf.readLine()+"1";
String str2 = "0"+bf.readLine()+"1";
index = 0;
String min1 = getMin(str1);
index = 0;
String min2 = getMin(str2);
if (min1.equals(min2)){
System.out.println("same");
}else {
System.out.println("different");
}
}
}
//0010011101001011
private static String getMin(String str1) {
List<String> strings = new ArrayList<>();
index++;
while (str1.charAt(index) == '0')strings.add(getMin(str1));
index++;
Collections.sort(strings);
StringBuilder sb = new StringBuilder();
sb.append("0");
for (String string : strings) {
sb.append(string);
}
sb.append("1");
return sb.toString();
}
}