我正在解决在codechef上找到Longest Palindrome的问题,并且编写了以下Java代码:
import java.io.*;
class Solution2 {
static String pal=""; //IT WILL HOLD THE LONGEST PALINDROME
public static void main(String[] args) throws IOException {
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
int n=Integer.parseInt(br.readLine());
int max=0;
String str=br.readLine();
if (n == 1) // PRINTS THE STRING IF THERE'S ONLY ONE LETTER
{
System.out.println(1);
System.out.println(str);
System.exit(0);
}
for (int i = 0; n - i > max && i < n; i++) { //(n-i) > MAX STOPS THE LOOP WHEN THE LENGTH OF
char ch = str.charAt(i); //PALINDROME IS GREATER THAN STRING LEFT TO PARSE
int ind = str.lastIndexOf(ch);
String sub = str.substring(i, ind + 1); //SUBSTRING THAT STARTS AND ENDS WITH THE SAME LETTER
int l = checkPalin(sub); //RETURNS THE LENGTH OF LONGEST PALINDROME IN SUBSTRING
if (l > max)
max = l;
}
System.out.println(max);
System.out.println(pal);
}
private static int checkPalin(String str) {
if(isPalin(str))
{
pal=str.length()>pal.length()?str:pal; // STORES THE LONGER PALINDROME STRING IN pal
return str.length(); // RETURNS THE LENGTH OF LONGEST SUBSTRING FOUND IN THE PASSED STRING
}
else
{
int last=str.substring(0,str.length()-1).lastIndexOf(str.charAt(0)); //RETURNS THE INDEX OF NEXT LAST CHARACTER
if (last==-1) //BY WHICH THE SUBSTRING STARTS
return 0;
return checkPalin(str.substring(0,last+1)); //RECURSIVELY SENDS THE REDUCED SUBSTRING
}
}
private static boolean isPalin(String str) { //RETURNS TRUE IF THE STRING IS PALINDROME, ELSE FALSE
int l=str.length()-1;
for (int i = 0; i < l; i++,l--) {
if (str.charAt(i)!=str.charAt(l))
return false;
}
return true;
}
}
所以,我的代码是这样的:它从字符串的第一个字母开始,然后从右边找到相同字母的索引。然后,它生成其子字符串并检查是否为回文。如果不是回文,则从右边开始寻找下一个索引,并重复生成子字符串和检查回文的过程。如果是回文,则从左转到下一个字母并重复相同的过程。重复该过程,直到重复的弦的长度大于尚未发现的最大回文的长度。但是,该解决方案未被codechef接受。我尝试了各种输入,但是在代码中找不到任何错误。
你很棒。你是我的英雄。我为你感到骄傲。