AcWing 779. 反转后求最长公共前缀再反转
原题链接
困难
作者:
还想听你的故事
,
2021-03-17 16:39:42
,
所有人可见
,
阅读 300
import java.util.*;
public class Main{
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
while(true){
int n=sc.nextInt();
if(n==0) break;
String s[]=new String[n];
for(int i=0;i<n;i++){
s[i]=sc.next();
}
String rev[]=new String[n];
for(int i=0;i<n;i++){
char c[]=s[i].toCharArray();
reverse(c,0,c.length-1);
rev[i]=new String(c);
}
String res=helper(rev);
char cc[]=res.toCharArray();
reverse(cc,0,cc.length-1);
System.out.println(new String(cc));
}
}
private static void reverse(char c[],int i,int j){
while(i<j) swap(c,i++,j--);
}
private static void swap(char c[],int i,int j){
char t=c[i];
c[i]=c[j];
c[j]=t;
}
//求最长公共前缀
private static String helper(String strs[]){
String res=strs[0];
for(String str:strs){
while(str.indexOf(res)!=0) res=res.substring(0,res.length()-1);
}
return res;
}
}