Find all words in a dictionary that can be made with a string of characters (Recursion/Binary Search) I'm working on an algorithm that could take in a string of 20 random characters, and display to the user every word in a dictionary that can be successfully made with those letters, regardless of length. If the string is "made", it would return "mad", "made", etc. 

However, the execution time is extremely poor with my current method. I've been recommended to give the Trie structure a shot. But seeing how Java doesn't have it built in, I wanted to see if there's a better approach to this algorithm, or if I should look at implementing my own Trie structure. 

I currently use a Binary Search implementation to check for prefixes, found through recursion, and see if a certain recursive path should be continued or not.

private ArrayList&lt;String&gt; dict = new ArrayList&lt;&gt;();
private Set&lt;String&gt; possibleWords = new HashSet&lt;&gt;();

private void getAllValidWords(String letterPool, String currWord) {
    //Add to possibleWords when valid word
    if (letterPool.equals("")) {
       // No action to be done.
    } else if(currWord.equals("")){
        //Will run only the initial time the method is called.
        for (int i = 0; i &lt; letterPool.length(); i++) {
            //Get the individual letters that will become the first letter of a word
            String curr = letterPool.substring(i, i+1);
            //Delete the single letter from letterPool
            String newLetterPool = (letterPool.substring(0, i) + letterPool.substring(i+1));
            if(inDict(curr)){
                possibleWords.add(curr);
            }
            boolean prefixInDic = binarySearch(curr);
            if(prefixInDic){
                //If the prefix isn't found, don't continue this recursive path.
                getAllValidWords(newLetterPool, curr);
            }
        }
    } else {
        //Every time we add a letter to currWord, delete from letterPool
        for(int i=0; i&lt;letterPool.length(); i++){
            String curr = currWord + letterPool.substring(i, i+1);
            String newLetterPool = (letterPool.substring(0, i) + letterPool.substring(i+1));
            if(inDict(curr)){
                possibleWords.add(curr);
            }
            boolean prefixInDic = binarySearch(curr);
            if(prefixInDic){
                //If the prefix isn't found, don't continue this recursive path.
                getAllValidWords(newLetterPool, curr);
            }
        }
    }
}

private boolean binarySearch(String word){
    int max = dict.size() - 1;
    int min = 0;
    int currIndex;
    boolean result = false;
    while(min &lt;= max) {
        currIndex = (min + max) / 2;
        if (dict.get(currIndex).startsWith(word)) {
            result = true;
            break;
        } else if (dict.get(currIndex).compareTo(word) &lt; 0) {
            min = currIndex + 1;
        } else if(dict.get(currIndex).compareTo(word) &gt; 0){
            max = currIndex - 1;
        } else {
            result = true;
            break;
        }
    }
    return result;
}
Favor interfaces over implementations


private ArrayList&lt;String&gt; dict = new ArrayList&lt;&gt;();



This would more commonly be written as 

private List&lt;String&gt; dict = new ArrayList&lt;&gt;();


Using the interface is more flexible and easier to change.  

Dictionary types

That said, the more common type for a dictionary is 

private Set&lt;String&gt; dictionary = new HashSet&lt;&gt;();


Then you can generate all the words and check them.  

If you are committed to a binary search, consider using a NavigableSet.  

private NavigableSet&lt;String&gt; dictionary = new TreeSet&lt;&gt;();


This would give you code like 

    for (char letter : letterPool.toCharArray()) {
        String current = word + letter;

        String bound = word + (letter + 1);
        NavigableSet&lt;String&gt; prefixed = dictionary.subSet(current, true, bound, false);

        if (prefixed.isEmpty()) {
            // no need to keep looking if we didn't find anything
            continue;
        }

        // current will be the first element of the Set if present
        if (prefixed.first.equals(current)) {
            possibleWords.add(current);
            prefixed.pollFirst();
        }

        // if there's more than one letter left in the pool
        if (letterPool.size &gt; 1) {
            // recurse with it out of the pool
            String remaining = letterPool.substring(0, i) + letterPool.substring(i + 1);
            getAllValidWords(remaining, current, prefixed);
        }
    }


I changed the names of currWord to word, newLetterPool to remaining, and curr to current, as I find that easier to read.  Your mileage may vary.  

We don't need to check if letterPool or word are empty.  The code works for those cases.  

I added prefixed to the recursive call.  The reason is that we don't need to search the whole tree.  We only need the subtree.  

I moved generation of newLetterPool to the point where I know it will be used.  Prior to that we may never use it, so why waste time generating it?  

Trie

This is the application for which a Trie is designed.  That said, my experience is that they tend to be slow and memory intensive.  It takes too long to build the structure to get the gains from fast prefix searches.  

You might well find the brute force solution with a HashSet to be faster.  In that solution, you basically generate each possible permutation and then filter out just the ones that are words.  The downside is that you may check a lot of words like zxqjv.  

A Trie works best in situations where it's prebuilt and easy to load into memory or where it stays as it is for long periods of time.  Also, you should not be memory constrained.  

If you do attempt to use a Trie, consider using it only for the first few letters.  Then you can go back to something more like this.