输入规格
你的程序需要
表示要测试的字符集的字符串字母数字输入中的所有字母均为小写(1≤长度≤500)
输出规格
根据输入,打印出可以从输入创建的唯一回文总数。
具体来说,假设我们有一个输入字符串“bbaa”,那么我们有回文“baab”,“abba”,所以由输入字符串“bbaa”创建的回文总数是2。下面是我写的代码,但是,它超过了时间限制,算法效率不高有没有人可以用某种方法来构造一个算法,这样我们就可以提高效率?
下面是我为这个问题写的:
import java.util.*;
import java.lang.*;
public class Problem
{
private static int count=0;
public static void main(String[] args)
{
Scanner stdin = new Scanner(System.in);
//int count=0;
while(stdin.hasNextLine())
{ String line=stdin.nextLine();
char[] line_char=line.toCharArray();
Arrays.sort(line_char);
StringBuilder strbuild=new StringBuilder("");
solve(line_char,new boolean[line_char.length],strbuild);
//System.out.println(stdin.nextLine());
}
System.out.println(count);
stdin.close();
}
public static void solve(char[] chararray,boolean[] used,StringBuilder strbuild){
if(strbuild.length()==chararray.length){
//System.out.println(strbuild.toString());
if(checkpalindrome(strbuild)){
count++;
}
}else{
char rec=(char)(chararray[chararray.length-1]+1);
for(int i=0;i<chararray.length;i++){
if(!used[i]&&rec!=chararray[i]){
rec=chararray[i];
strbuild.append(chararray[i]);
used[i]=true;
solve(chararray,used,strbuild);
strbuild.deleteCharAt(strbuild.length()-1);
used[i]=false;
}
}
}
}
public static boolean checkpalindrome(StringBuilder strbuild){
String str=strbuild.toString();
StringBuilder str1=new StringBuilder(strbuild);
return str.equals(str1.reverse().toString());
}
}
最佳答案
有一种更简单的计算回文的方法。我不打算为您编写代码,但我将描述这种方法。
由于必须使用输入的所有字符,因此最多只能有一个出现奇数次的字符。所以你应该先检查一下。如果有多个字母的计数是奇数,那么答案必须是零。否则,取奇数字母(如果有的话)并想象它在输出字符串的中间。然后所有剩余的字母出现偶数次。但现在生成回文相当于取每个字母计数的一半,并生成这些字母的所有唯一排列。然后,每个排列都会有一个回文,由排列、中间的字母(如果适用)和排列的反面组成。
所以你所要做的就是计算一半字母的所有唯一排列(在处理完单个奇数字母之后,如果有的话)。这应该比你现在的方法更容易做到。