5
\$\begingroup\$

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<String> dict = new ArrayList<>();
private Set<String> possibleWords = new HashSet<>();

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 < 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<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 <= max) {
        currIndex = (min + max) / 2;
        if (dict.get(currIndex).startsWith(word)) {
            result = true;
            break;
        } else if (dict.get(currIndex).compareTo(word) < 0) {
            min = currIndex + 1;
        } else if(dict.get(currIndex).compareTo(word) > 0){
            max = currIndex - 1;
        } else {
            result = true;
            break;
        }
    }
    return result;
}
\$\endgroup\$
  • \$\begingroup\$ For your example, would it also return "dame"? Assuming it's in the dictionary? I.e. can you swap the letters? Also, can the same letter appear more than once? \$\endgroup\$ – Emily L. Jun 21 '17 at 17:39
3
\$\begingroup\$

Check if you are solving the right problem!

Most times when codes get horribly slow, you are solving the wrong problem, or the problem in an ineffective way. Try to think of different approaches. It's hard when you are already down a certain path, but try to take some distance and approach from another angle.

Alternative solution

You should reverse the problem and see for each word in the dictionary if it can be made from the letters.

It then becomes a linear search through all the words. Which is nice :)

You can use anagram code like counting the frequency of the letters of your input to quickly check if a word can be matched. A match is when the frequencies of all letters in a word are at least matched by the input. You can quickly stop in the matching code if you find a frequency of a character that is not covered.

Example

I used this list: https://raw.githubusercontent.com/dwyl/english-words/master/words.txt

The program below executes within a second on my laptop.

Input: made

Output:

a
ad
ade
adm
ae
am
amd
ame
d
da
dae
dam
dame
de
dea
dem
dema
dm
dma
dme
e
ea
ead
eam
ed
eda
edam
edm
em
ema
emad
emda
m
ma
mad
made
mae
maed
md
mde
me
mea
mead
med
meda

Program:

public class Words
{
    public static void main( String[] args ) throws IOException
    {
        List<String> list = Files.readAllLines( new File( "/home/raudenaerde/words.txt" ).toPath(), Charset.defaultCharset() );

        List<String> lowercase = list.stream().map( s -> s.toLowerCase() ).filter( s->s.chars().allMatch(Character::isLetter)).collect( Collectors.toList() );

        System.out.println( "Read " + lowercase.size() + " words" );

        findOptions( "made", lowercase );
    }

    private static void findOptions( String string, List<String> lowercase )
    {
        int[] freq = toFreq( string );
        for ( String l : lowercase )
        {
            int[] freqIn = toFreq( l );
            if ( matches( freq, freqIn ) )
            {
                System.out.println( l );
            }
        }
    }

    /**
     * Returns true if all the frequencies of the letters match.
     * 
     * @param freq
     * @param freqIn
     * @return
     */
    private static boolean matches( int[] freq, int[] freqIn )
    {
        for ( int i = 0; i < 26; i++ )
        {
            if ( freq[i] == 0 && freqIn[i]>0)
            {
                return false;
            }
            else if (freq[i] < freqIn[i])
            {
                return false;
            }

        }
        return true;
    }

    /**
     * Encode a word in to a freqceny array. int[0] = #a's, int[1] = #b's etc.
     * 
     * @param string
     * @return
     */
    private static int[] toFreq( String string )
    {
        int[] freq = new int[26];
        for ( char c : string.toCharArray() )
        {
            if ( ( c - 'a' ) >= 0 && ( c - 'a' ) < 26 )
            {
                freq[c - 'a']++;
            }
        }
        return freq;
    }
}
\$\endgroup\$
  • \$\begingroup\$ That looks perfect! I'll definitely give this a shot to see if it makes my execution time bearable. Otherwise, I'll probably reduce the 20-char starting max and work on a replacement method for characters every turn or something. I had thought about doing the method you suggested, but I didn't spend much time considering it... I guess I thought recursion + binary search would be cooler or something... Thanks!! \$\endgroup\$ – Black Diamond Jun 22 '17 at 1:01
  • \$\begingroup\$ I expert the length of the input string does not even matter that much, as it will be turend in a frequency array straight away. It's might introduce slightly longer execution time in matches(), but actually I expect that effect to be negligible. \$\endgroup\$ – RobAu Jun 22 '17 at 5:51
  • \$\begingroup\$ BTW, I agree, binary search and recursion are cooler :) \$\endgroup\$ – RobAu Jun 22 '17 at 6:47
  • \$\begingroup\$ Nice idea, to move the searchee (the input string) and the search space word list (list) to a different realm that is tuned for finding matches. \$\endgroup\$ – glissi Jun 22 '17 at 11:08
  • \$\begingroup\$ I expect the preparation of the word list to be more costly than the actual search (depending on dictionary size). Should you expect to run findOptions more than once, I'd consider moving the preparation of the frequency array outside, store it in a map alongside the dictionary entries and reuse it.. \$\endgroup\$ – glissi Jun 22 '17 at 11:14
3
\$\begingroup\$

Favor interfaces over implementations

private ArrayList<String> dict = new ArrayList<>();

This would more commonly be written as

private List<String> dict = new ArrayList<>();

Using the interface is more flexible and easier to change.

Dictionary types

That said, the more common type for a dictionary is

private Set<String> dictionary = new HashSet<>();

Then you can generate all the words and check them.

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

private NavigableSet<String> dictionary = new TreeSet<>();

This would give you code like

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

        String bound = word + (letter + 1);
        NavigableSet<String> 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 > 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.

\$\endgroup\$
  • \$\begingroup\$ Thanks for catching that! I normally try to stick to interfaces but obviously missed it here... I'm definitely not set on a binary search implementation. The only reason that I implemented it was because I thought it would help reduce execution time over straight recursion. I don't really have any experience with Tree sets so I might give that a try for the sake of practice. I agree that from what I've seen, a Trie might not be the best in this case. However, this program is just for fun so I might give a Trie a try for the experience! Thanks again! \$\endgroup\$ – Black Diamond Jun 22 '17 at 1:07

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.