8
\$\begingroup\$

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;
    }
}
\$\endgroup\$
1
  • \$\begingroup\$ In general I would advise to use more helper functions, e.g. readWords, printPermutations. If you run into performance problems, using StringBuilder will be a rather big improvement when generating strings. \$\endgroup\$
    – Sulthan
    Nov 30, 2015 at 12:51

2 Answers 2

6
\$\begingroup\$

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);
    }
}
\$\endgroup\$
4
  • \$\begingroup\$ This option is going to be much slower on start, because of the sorting of each elements. But it's pretty damn solid afterwards. Good pick. I think it might be useful to some people if you added a little more wording to your algorithm! :) \$\endgroup\$
    – IEatBagels
    Nov 30, 2015 at 19:56
  • \$\begingroup\$ Tomorrow. Tired. \$\endgroup\$
    – coderodde
    Nov 30, 2015 at 19:58
  • \$\begingroup\$ if (map.containsKey(word)) part can be replaced with Map.merge(K, V, BiFunction) :). \$\endgroup\$
    – h.j.k.
    Dec 1, 2015 at 9:06
  • \$\begingroup\$ @coderodde Thanks. Finally got a chance to look at this. \$\endgroup\$
    – TheEditor
    Dec 1, 2015 at 11:04
1
\$\begingroup\$
  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();
  1. 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.)

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.