Finding permutations of a word

Question

This was a basic anagram problem. Take an input word, find all its permutations, then check a dictionary file to see what if any of those are real words.

Dictionary file

My input data:

8
lasting
lameness
severer
lapse
alerting
medical
tasking
crates

My answer:

3 3 3 5 4 4 3 6 

The code works slowly, as in, it took maybe a minute. Aside from any other criticism, I'm curious to the following:

1. Why are these two so different in speed? Casting as String was much faster:

   String current = (String) iter.next();
   

   and

   String current = iter.next().toString();
   

2. Is there a smarter way than looping through the dictionary every single time for every permutation of a word?

3. Is there a better data structure for the dictionary than an ArrayList? If so, why?

    package com.secryption.CA127Anagrams;

import java.util.*;
import java.io.File;

/**
 * Created by bmarkey on 11/26/15.
 */

public class Anagrams {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        Scanner inFile;
        System.out.println("Enter Data: ");
        int testCases = Integer.parseInt(in.nextLine());
        ArrayList<String> dictionary = new ArrayList<>();

        try {
            File file = new File("/home/me/words.txt");
            inFile = new Scanner(file);

            while (inFile.hasNextLine()) {
                dictionary.add(inFile.nextLine());
            }
            inFile.close();

        } catch (Exception e) {
            e.printStackTrace();
        }


        for (int i = 0; i < testCases; i++) {
            int counter = 0;
            String inputStr = in.nextLine();

            Set<String> allCombos = getPermutations(inputStr);

            Iterator iter = allCombos.iterator();

            while (iter.hasNext()) {
                String current = (String) iter.next();
//              String current = iter.next().toString();
                for( int j = 0; j < dictionary.size(); j++) {
                    if (current.equals(dictionary.get(j))) {
                        counter++;
                    }
                }
            }
            System.out.print((counter - 1) + " ");
        }

    }


    public static Set<String> getPermutations(String str) {
        Set<String> permResult = new HashSet<String>();

        if (str == null) {
            return null;
        } else if (str.length() == 0) {
            permResult.add("");
            return permResult;
        }

        char firstChar = str.charAt(0);
        String rem = str.substring(1);
        Set<String> words = getPermutations(rem);

        for (String newString : words) {
            for ( int i = 0; i <= newString.length(); i++) {
                permResult.add(permCharAdd(newString, firstChar, i));
            }
        }
        return permResult;
    }

    public static String permCharAdd(String str, char c, int j) {
        String first = str.substring(0, j);
        String last = str.substring(j);
        return first + c + last;
    }
}

Answer 1

The algorithm

Given two string \$S\$ and \$Z\$, \$S\$ is a permutation of \$Z\$ if and only if they have the same multiset of characters. The fastest way of checking this is to sort the characters in each of the two strings which will produce two new strings \$S'\$ and \$Z'\$. Finally, if \$S' = Z'\$, \$S\$ is a permutation of \$Z\$. For example: \$S = \text{stop}\$, \$Z = \text{spot}\$, \$S' = Z' = \text{opst}\$.

You can improve the performance:

Create a HashMap<String, Integer>, call it "map",
For each "word" in the word file, do:
    Sort "word" by characters ("fdsbs" -> "bdfss")
    If "word" is not in "map":
        Put "word" into "map" with value "1"
    Else:
        map.put(word, map.get(word) + 1) # Increment count

In order to process an input word, just sort it by characters and do a simple lookup from map. Summa summarum:

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

public class Anagrams {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        System.out.println("Enter number of test cases: ");
        int testCases = Integer.parseInt(in.nextLine());

        File file = new File("/path/to/words.txt");
        Map<String, Integer> map = readFile(file);

        for (int i = 0; i < testCases; i++) {
            String s = sort(in.nextLine());
            System.out.println(map.getOrDefault(s, 0) - 1);
        }
    }

    private static Map<String, Integer> readFile(File file) {
        Map<String, Integer> map = new HashMap<>();

        try (Scanner fileScanner = new Scanner(file)) {
            while (fileScanner.hasNext()) {
                String word = sort(fileScanner.next());

                if (map.containsKey(word)) {
                    map.put(word, map.get(word) + 1);
                } else {
                    map.put(word, 1);
                }
            }
        } catch (FileNotFoundException ex) {
            return null;
        }

        return map;
    }

    private static String sort(String input) {
        char[] chars = input.toCharArray();
        Arrays.sort(chars);
        return new String(chars);
    }
}

Answer 2

1. Why are these two so different in speed? Casting as String was much faster:

The cast is just a type check (1 or 2 JVM instructions), as iter.next()'s type should be String. The toString() call just does return this;, so it should be fast too. Actually, you can just write:

String current = iter.next();

Correction: you could if you change the line to:

Iterator<String> iter = allCombos.iterator();

3. Is there a better data structure for the dictionary than an ArrayList? If so, why?

Use a Set. Using an ArrayList, your check time is O(n). With a TreeSet, check time is O(log(n)). With a HashSet, check time is O(1). If you use HashSet, set the initial capacity correctly. (After all, in your case, you know how many items you are putting in it.)