java - 打印出列表中最长的回文

Question

我想知道是否有人可以指出正确的方向。

我有一个超过 400,000 个单词的外部文本文件，目的是打印出每个单词都是回文，我这样做了，但现在我想弄清楚如何从中收集 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 很好，但如果您的单词列表很长，它们的内存开销很大。如果您只需要 top-n 用于低 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)) - 但您的 n 是 10)，而不是字典的大小。最坏的情况是在前面插入，但是移动 9 个元素是相当便宜的，并且可能比 TreeMap traversal+insert 好得多。