打印出列表中最長的迴文

Question

我想知道是否有人能指引我走向正確的方向。

我有一個超過40萬字的外部文本文件，其目的是打印出每個詞是迴文，這是我做的，但現在我正試圖弄清楚如何收集10個最長的迴文所有印製在打印機上的副本，並將頂部10分開，並將它們打印到控制檯上。

如果有人能讓我開始，我畫空白！

這裏是我的代碼：

import java.io.File; 
import java.io.FileNotFoundException; 
import java.util.Scanner; 

public class Palindrome { 

    public static void main(String[] args) { 
    // store external text file into a new File object 
    File file = new File("dict.txt"); 

    try { 
     // new Scanner object to read external file 
     Scanner sc = new Scanner(file); 
     while (sc.hasNextLine()) { 
      // read each word so long as there is a word on subsequent line 
      String word = sc.nextLine(); 
      // if the word is a palindrome 
      if (isPalindrome(word)) { 
       // print out the palindrome word to console 
       System.out.println(word + " is a palindrome"); 
      } 
     } 
    } catch(FileNotFoundException fnfe) { 
     // if file is not found, print error to console 
     System.out.println(fnfe.toString()); 
    } 
    } // end main 

    public static boolean isPalindrome(String word) { 
    // if there is no word 
    if (word == null || word.length() == 0) { 
     // return false 
     return false; 
    } 
    // StringBuilder to hold a variable of the reverse of each word 
    String reverse = new StringBuilder(word).reverse().toString(); 
    // if the reversed word equals the original word 
    if (reverse.equals(word)) { 
     // it is a palindrome 
     return true; 
    } 

    // return false if no palindrome found 
    return false; 
    } // end isPalindrome 


} // end class Palindrome 

提前任何建議謝謝！

Answer 1

可以，例如，按大小收集的收集和他們組中所有的迴文：

Map<Integer, Set<String>> palindromes = new HashMap<>(); 

，當你發現一個迴文它添加有：

palindromes.computeIfAbsent(word.length(), f -> new HashSet<>()).add(word); 

在年底循環可以找到Map的最大鍵，在Set中你可以找到單詞。

Answer 2

可能有幾種方法可以實現這一點，但首先想到的是收集所有的迴文到一個集合中，然後按長度排序以找出10個最長的迴文。

因此在if塊調用isPalindrome內，您可以將word添加到您的集合中。然後在while循環之後，對列表進行排序。我不記得向默認的Java sort方法提供自定義排序規則有多容易/難。

Answer 3

套和地圖很好，但如果你的單詞列表很長，它們在內存中的代價很高。如果你只需要前n爲低電平（比如，N = 10）下面是多計數更好：

// to compare strings by reverse length, and then alphabetically 
private static final Comparator<String> lengthComparator = new Comparator<String>(){ 
    public int compare(String a, String b) { 
     int c = b.length() - a.length(); 
     return c==0 ? a.compareTo(b) : c; 
    } 
}; 

// to update the top-n list. Pass in an empty list at the start 
public static void updateTop10(String word, ArrayList<String> top, int n) { 
    int index = Collections.binarySearch(top, word, lengthComparator); 
    System.out.println("found at " + index + ": " + word); 
    if (index >= 0) { 
     // word already in list; no need to add it 
     return; 
    } else if (top.size()<n) { 
     // list not full - add it in 
     top.add(-1-index, word); 
    } else if (word.length() > top.get(n-1).length()) { 
     // larger than smallest word in list - insert into position 
     top.remove(n-1); 
     top.add(-1-index, word); 
    } 
} 

查找比套（O(log(n)）快 - 但你ñ 10） ，而不是字典的大小。最壞的情況是在前面插入，但是移動9個元素非常便宜，並且可能比遍歷+插入要好得多。