26
\$\begingroup\$

I'm trying to find all the 3, 4, 5, and 6 letter words given 6 letters. I am finding them by comparing every combination of the 6 letters to an ArrayList of words called sortedDictionary. I have worked on the code a good bit to get it to this point.

I tested how many six letter words are checked and got 720 which is good because 6*5*4*3*2*1=720 which means I am not checking any words twice. I can't make it faster by getting rid of duplicate checks because I have already gotten rid of them all.

Can I still make this faster?

Note that sortedDictionary only contains about 27 hundred words.

for(int l1 = 0; l1 < 6; l1++){
    for(int l2 = 0; l2 < 6; l2++){
        if(l2 != l1)
            for(int l3 = 0; l3 < 6; l3++){
                if(l3 != l1 && l3 != l2){
                    if(sortedDictionary.contains(""+anagramCharacters[l1]+anagramCharacters[l2]+anagramCharacters[l3]))
                        anagram_words.add(""+anagramCharacters[l1]+anagramCharacters[l2]+anagramCharacters[l3]);
                    for(int l4 = 0; l4 < 6; l4++){
                        if(l4 != l1 && l4 != l2 && l4 != l3){
                            if(sortedDictionary.contains(""+anagramCharacters[l1]+anagramCharacters[l2]+anagramCharacters[l3]+anagramCharacters[l4]))
                                anagram_words.add(""+anagramCharacters[l1]+anagramCharacters[l2]+anagramCharacters[l3]+anagramCharacters[l4]);
                            for(int l5 = 0; l5 < 6; l5++){
                                if(l5 != l1 && l5 != l2 && l5 != l3 && l5 != l4){
                                   if(sortedDictionary.contains(""+anagramCharacters[l1]+anagramCharacters[l2]+anagramCharacters[l3]+anagramCharacters[l4]+anagramCharacters[l5]))
                                       anagram_words.add(""+anagramCharacters[l1]+anagramCharacters[l2]+anagramCharacters[l3]+anagramCharacters[l4]+anagramCharacters[l5]);
                                   for(int l6 = 0; l6 < 6; l6++){
                                       if(l6 != l1 && l6 != l2 && l6 != l3 && l6 != l4 && l6 != l5)
                                           if(sortedDictionary.contains(""+anagramCharacters[l1]+anagramCharacters[l2]+anagramCharacters[l3]+anagramCharacters[l4]+anagramCharacters[l5]+anagramCharacters[l6]))
                                               anagram_words.add(""+anagramCharacters[l1]+anagramCharacters[l2]+anagramCharacters[l3]+anagramCharacters[l4]+anagramCharacters[l5]+anagramCharacters[l6]);
                                    }   
                                }
                            }   
                        }
                    }
                }
            }
    }
}

My solution, still probably not the best written code but it reduce the loading time from about 1-2 seconds to nearly instant (no noticeable wait time; didn't actually test how long it was).

for(int i = 0; i < sortedDictionary.size(); i++){
    for(int index = 0; index < anagram.length(); index++)
        anagramCharacters[index] = anagram.charAt(index);
    forloop:
    for(int i2 = 0; i2 < sortedDictionary.get(i).length(); i2++){
        for(int i3 = 0; i3 < anagramCharacters.length; i3++){
            if(sortedDictionary.get(i).charAt(i2) == anagramCharacters[i3]){
                anagramCharacters[i3] = 0;
                break;
            }
            else if(i3 == anagramCharacters.length-1)
                break forloop;
        }
        if(i2 == sortedDictionary.get(i).length()-1)
            anagram_words.add(sortedDictionary.get(i));
    }
}
\$\endgroup\$
  • 1
    \$\begingroup\$ Just to be sure: you can't use the same letter twice in a word? Unless some of the 6 letters are themselves duplicates? \$\endgroup\$ – toto2 Nov 28 '13 at 17:48
  • 2
    \$\begingroup\$ The only "it" you need to speed up is how long it takes to understand the code. Seriously, splitting this into subroutines will hep you speed the code up by helping you understand what the code actually does. \$\endgroup\$ – AJMansfield Nov 29 '13 at 1:33
13
\$\begingroup\$

if the number of words in the dictionary is small then you might be better off turning the code around and going over the words in the dictionary and checking if the words there have the 6 letters

disregarding that you recreate the string several times it would be more efficient to keep the prefix in a char array

char[] prefix= new char[6];
for(int l1 = 0; l1 < 6; l1++){
    prefix[0]=anagramCharacters[l1];
    for(int l2 = 0; l2 < 6; l2++)
        if(l2 != l1){
        prefix[1]=anagramCharacters[l2];

then you can create the string with new String(prefix,0,3) (replace the 3 with the length)

otherwise recursion to the rescue:

List<String> createAnagrams(char[] chars, SortedSet<String> sortedDictionary){
    List<String result = new ArrayList<String>();
    fillListWithAnagrams(result, sortedDictionary, chars, 0);
    return result;
}

void fillListWithAnagrams(List<String> result, SortedSet<String> sortedDictionary, char[] chars, int charIndex){
    if(charIndex>=3){
       String resultString = new String(chars,0,charIndex);
       if(sortedDictionary.contains(resultString);
           list.add(resultString);
    }

    if(charIndex>=chars.length)
       return;//end of the line

    for(int i = charIndex;i<chars.length;i++){
        char t = chars[i];
        chars[i] = chars[charIndex];
        chars[charIndex] = t;

        fillListWithAnagrams(list, sortedDictionary, chars, charIndex+1);

        // revert the char array for the next step
        //t=chars[charIndex];
        chars[charIndex] = chars[i];
        chars[i] = t;
    }

}

\$\endgroup\$
36
\$\begingroup\$

Before I get started I have to say: Thank you for coming here. Mess of Java For Loops is almost an understatement. Now, let's get working, shall we?

In the below answer I assume that sortedDictionary and anagram_words is both of type List<String>. I also assume that anagramCharacters is of type char[].

Code duplication

Start by identifying which parts of the code looks similar, and create some methods to reduce code duplication

Code like this is repeated several times:

if(sortedDictionary.contains(""+anagramCharacters[l1]+anagramCharacters[l2]+anagramCharacters[l3]))
     anagram_words.add(""+anagramCharacters[l1]+anagramCharacters[l2]+anagramCharacters[l3]);

This can be extracted to a method: addWord() (Note that the below method is not optimized for what it is doing, it is mainly so that you are able to understand what it does better).

private void addWord(char... chars) {
    String string = "";
    for (char ch : chars) string += ch; // Create a strings of the chars
    if (sortedDictionary.contains(string))
        anagram_words.add(string);
}

So instead of repeatedly writing

if (sortedDictionary.contains(....)) anagram_words.add(...)

we simply call a method:

addWord(anagramCharacters[l1], anagramCharacters[l2], anagramCharacters[l3]);

Variables with index

Whenever you find yourself using variable names that contains numbered values, such as l1, l2, l3, l4, STOP and think "Would an array be useful here?". Creating an int[] letters is far more flexible than using the multiple variables l1, l2, l3

If all the l-variables are instead inside the letters array, some things can be simplified further at the moment:

  • This:

    if(l4 != l1 && l4 != l2 && l4 != l3)
    

    would become

    if(letters[3] != letters[0] && letters[3] != letters[1] && letters[3] != letters[2])
    
  • This:

    if(letters[3] != letters[0] && letters[3] != letters[1] && letters[3] != letters[2])
    

    can become a method

    private boolean lastLetterDifferent(int index) {
        for (int i = 0; i < index; i++) {
            if (letters[i] == letters[index]) return false;
        }
        return true;
    }
    
  • The previous call we made to addWord only needs to contain the number of indexes to check instead of each and every char.

    private void addWord(int numberOfChars) {
        String string = "";
        for (int i = 0; i < numberOfChars; i++) string += anagramCharacters[letters[i]]; // Create a strings of the chars
        if (sortedDictionary.contains(string))
            anagram_words.add(string);
    }
    

So now that's done, what remains now?

After doing the above refactoring, here is what's left:

for(letters[0] = 0; letters[0] < 6; letters[0]++){
    for(letters[1] = 0; letters[1] < 6; letters[1]++) {
        if(lastLetterDifferent(1)) {
            for(letters[2] = 0; letters[2] < 6; letters[2]++) {
                if(letters[2] != letters[0] && letters[2] != letters[1]) {
                    addWord(3);
                    for(letters[3] = 0; letters[3] < 6; letters[3]++) {
                        if (lastLetterDifferent(3)) {
                            addWord(4);
                            for(letters[4] = 0; letters[4] < 6; letters[4]++){
                                if (lastLetterDifferent(4)) {
                                    addWord(5);
                                    for(letters[5] = 0; letters[5] < 6; letters[5]++){
                                        if (lastLetterDifferent(5)) {
                                            addWord(6);
                                        }
                                    }   
                                }
                            }   
                        }
                    }
                }
            }
        }
    }
}

That looks a lot cleaner, but how flexible is this? What if we want to use an 8-letter word, or a 12-letter word? NO, you should NOT continue this pattern and add more for-loops! So what other alternative is there? Recursive methods, my friend!

To do this, we need a couple of helper methods. You mentioned the number 720. It just so happens that 720 equals 6 factorial. So let's create a factorial method.

public static int fact(int x) {
    if (x < 0) throw new IllegalArgumentException("x cannot be negative: " + x);
    if (x <= 1) return 1;
    return x * fact(x - 1);
}

This is a recursive because it calls itself on some occasions. More precisely, when x >= 2. Recursive methods are fun, so let's create another one!

public static <E> List<E> permutationI(List<E> values, int iteration) {
    if (values.size() == 0)
        return new ArrayList<E>();
    List<E> list = new ArrayList<E>(values.size());
    int divisor = fact(values.size() - 1);
    int pos = iteration / divisor; // Pick an index depending on the iteration value
    list.add(values.remove((int)pos)); // Remove from one list and add to another
    list.addAll(permutationI(values, iteration % divisor)); // Call method recursively to get all the elements
    return list;
}

Every time this method is called, it picks an index in the values list depending on the value of iteration. Then it gets the element for that index from the values list, removes that element from the values list and adds it to the list called list (which will be the methods result. Then this method calls itself to add all the remaining elements for the current iteration.

Putting it together:

We will need one more utility method to convert from a List of characters to a String (again, this method is not fully optimized. There are plenty of faster ways to do this).

public String charListToString(List<Character> list) {
    String result = "";
    for (Character ch : list) {
        result += ch;
    }
    return result;
}

And now, the final touch to use all this recursive-ness:

List<Character> indexes = new ArrayList<Character>();
for (char ch : anagramCharacters)
    indexes.add(ch); // Build a list of the characters in our original word
int totalPermutations = fact(indexes.size());
for (int i = 0; i < totalPermutations; i++) {
    // Since permutationI modifies the list we send, we copy the list
    List<Character> newList = permutationI(new ArrayList<Character>(indexes), i);
    addWord(charListToString(newList)); // Call our method to add the word to the result list
}
\$\endgroup\$
  • 3
    \$\begingroup\$ Thanks for the detailed response, I will read this all over when I get the chance as my coding style does need improving. I found a solution to my problem by someone else suggestion, but this is definitely the most informative post. +1 and the internet needs more people like you :) thanks! \$\endgroup\$ – java Nov 28 '13 at 18:32
  • 1
    \$\begingroup\$ Instead of using a loop to add characters to a string, you really ought to be using the new String(char []) constructor. \$\endgroup\$ – AJMansfield Nov 29 '13 at 1:39
  • \$\begingroup\$ OK, just edited to use the String constructor where possibe, and StringBuilder otherwise; also added the null check to the method to convert the char list to a string. \$\endgroup\$ – AJMansfield Nov 29 '13 at 1:50
  • \$\begingroup\$ What @AJMansfield said. docs.oracle.com/javase/7/docs/api/java/lang/…. Other than that the answer is great. \$\endgroup\$ – Aseem Bansal Nov 29 '13 at 18:39
  • \$\begingroup\$ @AseemBansal I am aware that such things can be improved here. I didn't want to improve too much, only focus on the most important things. I thought that using String and iteratively adding to it is more comprehensive for the OP. \$\endgroup\$ – Simon Forsberg Dec 3 '13 at 21:26
14
\$\begingroup\$

This problem begs for recursion....

private static final void checkWord(char[] chars, char[]current, int len, List<String> results) {
    if (len == chars.length) {
        final String result = new String(current);
        if (sortedDictionary.contains(result)) {
             results.add(result);
        }
    } else {
        // get the next combination for what is left in the chars
        for int (i = xx; i < yy; i++) {
            current[len] = .... // next char to try
            checkWord(chars, current, len+1 results);
        }
    }
}

EDIT

This is a 'nice' problem, it ties in all the favourite educational problems, factorial, combinations, and permutations...

Here is working code that runs through the process.... I have commented it where I think necessary. I am doing this so that I have a record on here of what things are, and can refer back to it later, if needed.:

import java.io.IOException;
import java.nio.charset.StandardCharsets;
import java.nio.file.Files;
import java.nio.file.Paths;
import java.util.Arrays;
import java.util.Collection;
import java.util.Set;
import java.util.TreeSet;


public class Words {

    /**
     * Calculate all possible ways to permute data sets of up to 'max' values...
     * <p>
     * The result is a multi-dimensional array, with result[2] being the ways to
     * permute 2-sized data sets ([1,2],[2,1]), and result[3] the way to permute 3-sized sets:
     * ([1,2,3],[1,3,2],[2,3,1],[2,1,3],[3,1,2],[3,2,1]),
     * etc.
     * 
     * @param max the largest set to calculate permutations for.
     * @return the possible ways to permute sets of values up to max values in size
     */
    private static final int[][][] permutations(int max) {
        int[][][] ret = new int[max + 1][][];
        ret[0] = new int[0][];
        ret[1] = new int[1][1];
        for (int i = 2; i <= max; i++) {
            ret[i] = new int[factorial(i)][];
            int[] remaining = new int[i];
            for (int j = 0; j < i; j++) {
                remaining[j] = j;
            }
            permutationGen(i, ret[i], 0, new int[0], remaining);
        }
        return ret;
    }

    /**
     * calculate the factorial of a number.
     * The factorial is the number of permutations available for a given set of values.
     * @param n the number to calculate
     * @return the factorial (n!)
     */
    private static int factorial(int n) {
        int ret = n;
        while (--n > 1) {
            ret *= n;
        }
        return ret;
    }

    /**
     * Recursive function to calculate the permutations of a dataset of a specified size.
     * @param size The number of elements to calculate the permutations for
     * @param store The place to store the permutations
     * @param nextstore the next location to save values in the store
     * @param used the positions that have been used in already in building the current permutations
     * @param remaining the remaining positions that need to be used.
     * @return the index of the next permutation to save
     */
    private static int permutationGen(final int size, final int[][] store, int nextstore, final int[] used, final int[] remaining) {

        if (used.length == size) {
            store[nextstore] = used;
            return nextstore + 1;
        }
        int [] nremain = Arrays.copyOfRange(remaining, 1, remaining.length);
        for (int r = 0; r < remaining.length; r++) {
            int [] nused = Arrays.copyOf(used, used.length + 1);
            if (r > 0) {
                nremain[r - 1] = remaining[r - 1];
            }
            nused[used.length] = remaining[r];
            nextstore = permutationGen(size, store, nextstore, nused, nremain);

        }
        return nextstore; 
    }

    /**
     * Recursive combination function. It determines all possible combinations for a set of data, and for
     * each combination it also then runs through all permutations.
     * With the permutations it checks to see whether the word created by that combination/permutation is
     * a real word, and if it is, it adds it to the anagrams solution set.
     * @param words the valid words
     * @param chars the actual characters we can use to anagram
     * @param charpos the position in the chars that we are currently processing
     * @param current the letters we currently have in our combination already.
     * @param currentlen the number of letters in current that are valid.
     * @param permutes the possible permutations for different-sized datasets.
     * @param anagrams where to store the valid words when we find them.
     */
    private static void checkCombinations(final String[] words, final char[] chars, final int charpos,
            final char[] current, final int currentlen, final int[][][] permutes, final Collection<String> anagrams) {

        if (currentlen >= current.length) {
            return;
        }

        for (int i = charpos; i < chars.length; i++) {
            current[currentlen] = chars[i];

            // This is th recursive function to calculate combinations.
            checkCombinations(words, chars, i + 1, current, currentlen + 1, permutes, anagrams);

            // for each combination, run through all the permutations.
            char[] strchr = new char[currentlen + 1];
            for (int[] perm : permutes[currentlen + 1]) {
                for (int j = 0; j <= currentlen; j++) {
                    strchr[j] = current[perm[j]];
                }
                String word = new String(strchr);
                if (Arrays.binarySearch(words, word) >= 0) {
                    anagrams.add(word);
                }
            }

        }

    }

    public static void main(String[] args) throws IOException {
        System.out.println("Reading Linux words file (typically /usr/share/dict/linux.words)");
        String words[] = Files.readAllLines(Paths.get("linux.words"), StandardCharsets.UTF_8).toArray(new String[0]);
        System.out.println("Convert all to lowercase");
        for (int i = 0; i < words.length; i++) {
            words[i] = words[i].toLowerCase();
        }
        System.out.println("Sort all words (" + words.length + ")");
        Arrays.sort(words);
        char[] chars = "abcdef".toLowerCase().toCharArray();

        Set<String> anagrams = new TreeSet<>();

        System.out.println("building permutations for " + chars.length + " sizes");
        int[][][] permutations = permutations(chars.length);

        System.out.println("calculating combinations and permutations of '" + new String(chars) + "'.");
        long time = System.nanoTime();
        checkCombinations(words, chars, 0, new char[chars.length], 0, permutations, anagrams);
        System.out.printf("Found %d words.... in %.3fms\n", anagrams.size(), (System.nanoTime() - time) / 1000000.0);
        for (String s : anagrams) {
            System.out.println(s);
        }

    }

}
\$\endgroup\$
7
\$\begingroup\$

The nested for-loops are not your only problem. Even if you could restructure the code to avoid nesting, you would still be left with a scalability problem from the combinatoric explosion. In other words, the fact that you may need to check 6! = 720 dictionary entries for each six-letter word is the fundamental issue. You need a new algorithm: one that checks validity without generating all the possibilities.

I propose that you sort the list of six valid letters. Then check whether the sorted letters of each candidate word are a subsequence of your sorted valid letters. (Subsequence is like substring, but with possible gaps.)

public static List<String> findWords(char[] letters, List<String> sortedDictionary) {
    letters = Arrays.copyOf(letters, letters.length);
    Arrays.sort(letters);
    char[] buf = new char[letters.length];

    List<String> anagramWords = new ArrayList<String>();
    for (String word : sortedDictionary) {
        int len = word.length();
        if (len < 3 || len > letters.length) {
            continue;
        }
        word.getChars(0, len, buf, 0);
        Arrays.sort(buf, 0, len);
        if (isSubsequence(buf, len, letters)) {
            anagramWords.add(word);
        }
    }
    return anagramWords;
}

private static boolean isSubsequence(char[] needle, int needleLen, char[] haystack) {
    for (int n = 0, h = 0; n < needleLen && h < haystack.length; n++, h++) {
        while (needle[n] > haystack[h]) {
            h++;
            if (h >= haystack.length) {
                return false;
            }
        }
        if (needle[n] < haystack[h]) {
            return false;
        }
        assert needle[n] == haystack[h];
    }
    return true;
}
\$\endgroup\$
6
\$\begingroup\$

Once you realised that you were permuting the characters you should have stopped there and worked out how to do that in a general way.

Here is a base class for permutations iteration:

public abstract class PermutationsIterator implements Iterator<List<Integer>> {
  // Length of the lists required.
  protected final int length;
  // The working list.
  protected final List<Integer> indexes;
  // The next to deliver.
  private List<Integer> next = null;

  public PermutationsIterator(int length) {
    this.length = length;
    indexes = new ArrayList<>(length);
    for (int i = 0; i < length; i++) {
      indexes.add(i);
    }
    // Deliver the base one first.
    this.next = Collections.unmodifiableList(indexes);
  }

  // Return true if a next was available.
  protected abstract boolean getNext();

  @Override
  public boolean hasNext() {
    if (next == null) {
      // Is there one?
      if ( getNext() ) {
          // That's next!
          next = Collections.unmodifiableList(indexes);
      }
    }
    return next != null;
  }

  @Override
  public List<Integer> next() {
    List<Integer> n = hasNext() ? next : null;
    next = null;
    return n;
  }

  @Override
  public void remove() {
    throw new UnsupportedOperationException("Cannot remove from permutations");
  }

}

From there you can implement a simple lexicographic iterator like this:

public class LexicographicPermutationsIterator extends PermutationsIterator implements Iterator<List<Integer>> {

  public LexicographicPermutationsIterator(int length) {
    super(length);
  }

  @Override
  protected boolean getNext() {
    boolean got = false;
    // Find the largest index k such that a[k] < a[k + 1]. If no such index exists, the permutation is the last permutation.
    int k = -1;
    for (int i = 0; i < length - 1; i++) {
      if (indexes.get(i) < indexes.get(i + 1)) {
        k = i;
      }
    }
    if (k >= 0) {
      int ak = indexes.get(k);
      // Find the largest index l such that a[k] < a[l].
      int l = k + 1;
      for (int i = 0; i < length; i++) {
        if (ak < indexes.get(i)) {
          l = i;
        }
      }
      // Swap the value of a[k] with that of a[l].
      Collections.swap(indexes, k, l);
      // Reverse the sequence from a[k + 1] up to and including the final element a[n].
      Collections.reverse(indexes.subList(k + 1, indexes.size()));
      // We got one.
      got = true;
    }
    return got;
  }

}

and you can then work out your anagrams with something as simple as:

public static void main(String args[]) {
  String testWord = "ABCDEF";
  Iterator<List<Integer>> it = new LexicographicPermutationsIterator(testWord.length());
  StringBuilder s = new StringBuilder(testWord.length());
  while ( it.hasNext() ) {
    List<Integer> p = it.next();
    s.setLength(0);
    for ( Integer i : p ) {
      s.append(testWord.charAt(i));
    }
    System.out.println(s);
  }
}
\$\endgroup\$
3
\$\begingroup\$

As the order doesn't matter, you can look at all the sorted words instead. You can also prebuild an index and make sure the code is warmer. Looking at a dictionary of 22K words, it takes an average of 9 micro-seconds on my laptop

This is faster because there is only 42 combinations of sorted letters which have a length of 3 to 6 and each lookup is O(1) so it doesn't need to scan all the words.

BTW If you want to improve the performance of some code you really have to time it because often you might change something assuming it will be faster and it is not. If you don't measure performance, you are guessing.

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.util.*;

public class WordsSearchMain {
    public static void main(String... ignored) throws IOException {
        Dictionary dict = new Dictionary("/usr/share/dict/words", 3, 6);
        final String alphabet = "abcdefghifjklmnopqrstuvwxyz";
        String[] words = new String[22];
        for (int i = 0; i < words.length; i++)
            words[i] = alphabet.substring(i, i + 6);

        // warmup the code
        for (int i = 0; i < 12000; i += words.length)
            for (String word : words)
                dict.allWordsFor(word);
        // time to do 20 searches
        Map<String, Set<String>> searches = new LinkedHashMap<>();
        long start = System.nanoTime();
        for (String word : words)
            searches.put(word, dict.allWordsFor(word));
        long time = System.nanoTime() - start;

        System.out.printf("Took an average of %.1f micro-seconds, searching %,d words%n",
                time / words.length / 1e3, dict.count);
        for (Map.Entry<String, Set<String>> entry : searches.entrySet()) {
            System.out.println(entry);
        }
    }

}

class Dictionary {
    private final int min;
    Map<String, List<String>> wordForLetters = new HashMap<>();
    int count = 0;

    public Dictionary(String filename, int min, int max) throws IOException {
        this.min = min;
        try (BufferedReader br = new BufferedReader(new FileReader(filename))) {
            for (String line; (line = br.readLine()) != null; ) {
                if (line.length() >= min && line.length() <= max) {
                    char[] chars = line.toLowerCase().toCharArray();
                    Arrays.sort(chars);
                    String sorted = new String(chars);
                    List<String> words = wordForLetters.get(sorted);
                    if (words == null)
                        wordForLetters.put(sorted, words = new ArrayList<>());
                    words.add(line);
                    count++;
                }
            }
        }
    }

    public Set<String> allWordsFor(String s) {
        Set<String> allWords = new TreeSet<>();
        String lower = s.toLowerCase();
        for (int i = (1 << min) - 1; i < (1 << s.length()); i++) {
            int bitCount = Integer.bitCount(i);
            if (bitCount < min) continue;
            StringBuilder sb = new StringBuilder(bitCount);
            for (int j = 0; j < s.length(); j++)
                if (((i >> j) & 1) != 0)
                    sb.append(lower.charAt(j));
            final List<String> words = wordForLetters.get(sb.toString());
            if (words != null)
                allWords.addAll(words);
        }
        return allWords;
    }
}

Prints

Took an average of 9.1 micro-seconds, searching 22,299 words
abcdef=[Abe, Dec, Feb, Fed, abed, ace, aced, bad, bade, bead, bed, cab, cad, dab, deaf, deb, decaf, face, faced, fad, fade, fed]
bcdefg=[Dec, Feb, Fed, bed, beg, deb, fed]
cdefgh=[Che, Dec, Fed, chef, fed]
defghi=[Fed, Gide, die, dig, fed, fie, fig, hid, hide, hie, hied]
efghif=[fie, fig, hie]
fghifj=[fig, jig]
ghifjk=[JFK, jig]
hifjkl=[JFK, ilk]
ifjklm=[JFK, Jim, Kim, ilk, mil, milk]
fjklmn=[JFK]
jklmno=[Jon, Lon, Mon, Monk, monk]
klmnop=[Lon, Mon, Monk, Polk, lop, monk, mop, pol]
lmnopq=[Lon, Mon, Qom, lop, mop, pol]
mnopqr=[Mon, Qom, Ron, mop, morn, nor, norm, porn, pro, prom, romp]
nopqrs=[Ron, Son, nor, porn, pro, pros, son, sop]
opqrst=[Post, opt, opts, port, ports, post, pot, pots, pro, pros, rot, rots, sop, sort, sot, sport, spot, stop, strop, top, tops, tor, tors]
pqrstu=[Prut, Stu, pus, put, puts, rust, rut, ruts, spur, spurt, sup, ups]
qrstuv=[Stu, rust, rut, ruts]
rstuvw=[Stu, rust, rut, ruts]
stuvwx=[Stu, tux]
tuvwxy=[tux]
uvwxyz=[]
\$\endgroup\$
0
\$\begingroup\$

First, let's consider the numbers.

You have 720 anagrams to check, and 2700 words. Instead of generating all anagrams and look them up, you can scan all words and see if they are "included" in the letters you have. You are trading one expensive lookup with 4 iterations in a loop. That might be faster.

That is why I will comment your second code fragment. I think it was a good start.

  1. A loop over a collection can be written in a more compact style. Also. declaring a variable for the word avoids recomputing sortedDictionary.get(i) many times.
  2. Extracting chars from a String can be expressed with string.toCharArray().
  3. You can also test from outside the loop whether you completed the loop. The break out of a named loop isn't necessary.
  4. It is usually better to save to a local variable an expression like word.getCharAt(i) instead of recomputing it over and over. Not sure whether it is a big difference for getCharAt, though.

So far we have

    for(String word : sortedDictionary){
        char[] anagramCharacters = anagram.toCharArray();
        int i2, i3;
        for(i2 = 0; i2 < word.length(); i2++){
            char wordChar = word.charAt(i2);
            for(i3 = 0; i3 < anagramCharacters.length; i3++){
                if(wordChar == anagramCharacters[i3]){
                    anagramCharacters[i3] = 0;
                    break;
                }
            }
            // break out if wordChar did not match any anagramCharacters
            if(i3 == anagramCharacters.length)
                break;
        }
        // add the word if all letters were found in the anagram letters
        if(i2 == word.length())
            anagram_words.add(word);
    }

But I am still not happy with it. I prefer to control the program flow using boolean variables. They somehow explain the why of the execution flow.

    for(String word : sortedDictionary){
        char[] anagramCharacters = anagram.toCharArray();
        boolean anagramOK = true;
        for(char wordChar : word.toCharArray()){
            boolean found = false;
            for(int i = 0; !found && i < anagramCharacters.length; i++){
                if(wordChar == anagramCharacters[i]){
                    anagramCharacters[i] = 0;
                    found = true;
                }
            }
            // if not found, the word is not compatible with the anagram letters
            if(!found){
                anagramOK = false;
                break;
            }
        }
        // add the word if all letters were found in the anagram letters
        if(anagramOK)
            anagram_words.add(word);
    }

PS: and yes, some people prefer brackets around every statement.

\$\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.