如何計算由字符串中的字符組成的迴文數？

您的程序將花費字符串S表示要測試的字符集。在字母數字輸入的所有字母將被小寫（1個≤LENGTH（S）≤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()); 
}

}

來源

2016-12-16 user144600

假設我們只有一個輸入字符串！這就是爲什麼我把System.out.println（count）;最後！ – user144600

@GurwinderSingh - 不是重複的，因爲OP允許重新排列輸入字母。你鏈接的問題是找到所有的迴文串。 –

迴文不得不使用所有的輸入字母嗎？我猜測是這樣的，因爲除此之外，如果您的示例輸入中還有迴文「a」，「b」，「aa」和「bb」（更不用說空字符串，如果這被認爲是迴文）。但值得提問。 –

有計數迴文一個更簡單的方法。我不會爲你寫代碼，但我會描述這種方法。

由於您必須使用輸入的所有字符，因此您最多隻能有一個出現奇數次的字符。所以你應該首先檢查這種情況。如果有不止一個字母的奇數，那麼答案必須爲零。否則，請將奇數字（如果有的話）想象爲輸出字符串的中間。然後所有剩餘的字母出現偶數次。但是現在生成迴文相當於每個字母數的一半，並生成這些字母的所有獨特排列。每個排列都有一個迴文，由排列，中間的字母（如果適用）和排列的相反組成。

所以你所要做的就是計算所有字母的一半排列（在處理單個單個字母后）。這應該比現在的方法更容易做得更有效率。

來源

2016-12-16 03:37:25

如何計算由字符串中的字符組成的迴文數？

回答

相關問題