我的思路和大家的都不同,我是时刻更新所在括号的层数,遇到 ( +1,反之-1,然后遍历两个数组看看能不能按顺序分布,如果可以完全对应输出possible,但是通过率只有92%,有没有大佬看看
import java.util.*;
public class Main{
public static void main(String[]args){
Scanner s =new Scanner(System.in);
String S=s.next();
String T=s.next();
int i,j,index=1;
int dps[]=new int[S.length()+1];
int dpt[]=new int[T.length()+1];
for(i=0;i<S.length();i++){
if(S.charAt(i)=='('){
dps[i+1]=dps[i]+1;
}
else if(S.charAt(i)==')'){
dps[i+1]=dps[i]-1;
}
}
for(i=0;i<T.length();i++){
if(T.charAt(i)=='('){
dpt[i+1]=dpt[i]+1;
}
else if(T.charAt(i)==')'){
dpt[i+1]=dpt[i]-1;
}
}
int count=0;
for(i=1;i<=T.length();i++){
for(j=index;j<=S.length();j++){
if(dps[j]==dpt[i]){
index=j+1;
count++;
break;
}
}
}
if(count==T.length())System.out.println("Possible");
else System.out.println("Impossible");
}
}
全部评论
(0) 回帖