2

I was wondering if someone could point me in the right direction.

I have an external text file with like over 400,000 words, and the aim is to print out each word that is a palindrome, which I did, but now I am trying to figure out how to collect the 10 longest palindromes out of all the palindromes which are printed to the console, and separate the top 10, by printing them to the console as well.

If someone could get me started, I'm drawing a blank!

Here is the code I have:

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

Thanks in advance for any advice!

Lushmoney
  • 412
  • 11
  • 26

3 Answers3

1

Sets and maps are nice, but if your word-list is long, they are expensive in memory. If you only need top-n for low n (say, n=10) the following is better on multiple counts:

// 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);
    }
}

Lookup is faster than in sets (O(log(n)) - but your n is 10), not the size of the dictionary. Worst-case are inserts at the front, but moving 9 elements over is quite cheap, and probably much better than TreeMap traversal+insert.

tucuxi
  • 17,561
  • 2
  • 43
  • 74
  • 1
    Managed to make this build (has errors) but it crashes. Also the comparator uses the size so assumes two different words with the same size are the same word, that is not correct. – gfelisberto Mar 02 '16 at 16:44
  • 1
    You are right - fixed. I had not actually tested the code, and there were multiple typos, plus the comparator error. – tucuxi Mar 02 '16 at 16:56
  • Thanks for the help. Never used Comparator before, and that looks pretty complex. I thought for sure there would be an easier method to get it done, and I was just having a brain fart in not being able to get it, but I guess it's a little harder than I anticipated. Not exactly sure where or how to implement something like this. Thank you though... – Lushmoney Mar 02 '16 at 17:40
0

You can, for example, collect all your palindromes in a collection and group them by size:

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

when you find a palindrome add it there:

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

At the end of the loop you can find the largest keys of the Map and in the Set you have the words.

gfelisberto
  • 1,655
  • 11
  • 18
  • @tucuxi: Yes it does, there were no requirements on space or time. There are many optimizations possible, one could store the current min-size of the Top 10 palindromes and not even go and validate if a word <= is a palindrome. – gfelisberto Mar 02 '16 at 16:44
  • Generally, it is considered better to write more efficient code, both space and time-wise. Therefore, while your answer technically works, I feel it can be improved. Hence the comment. – tucuxi Mar 02 '16 at 16:46
0

There are probably several ways to accomplish this, but the first one that comes to mind is to collect all of the palindromes into a collection, and then sort them by length to find the 10 longest.

So inside the if block call to isPalindrome, you can add the word to your collection. And then after your while loop, sort the list. I can't remember how easy/hard it is to provide custom sort rules to the default Java sort method.

Brian J
  • 694
  • 1
  • 21
  • 34