Find meaningful words from the input string

Question

Given a string find the number of meaningful words which could be formed from the string for eg. programmerit forms:

pro+gram+merit
program+merit
programmer+it
pro+grammer+it

Looking for code review optimizations and best practices. Also hoping for suggestions for complexity better than \$O(n^2)\$, where n is the number of characters.

public final class DictionaryValidWords {

    private static final Set<String> dictionary = new TreeSet<String>();
    static {
        dictionary.add("this");
        dictionary.add("his");
        dictionary.add("is");
        dictionary.add("awe");
        dictionary.add("we");
        dictionary.add("some");
        dictionary.add("awesome");
        dictionary.add("foo");
        dictionary.add("bar");
    }

    private DictionaryValidWords() {}

    /**
     * Returns set of valid words given an input string.
     * It eliminates duplicates.
     * 
     * @param str   The input string whose valid words need to be found out.
     * @return      List of valid words nested in the string.
     */
    public static Set<String> findValidStrings(String str) {
        if (str.length() ==  0) {
            throw new IllegalArgumentException("Strings of length 0 are illegal");
        }

        final Set<String> validWords = new HashSet<String>(); 
        for (int i = 0; i < str.length(); i++) {
            StringBuilder sb = new StringBuilder();
            for (int j = i; j < str.length(); j++) {
                sb.append(str.charAt(j)); // O(1) complexity.
                if (dictionary.contains(sb.toString())) {
                    validWords.add(sb.toString());
                }
            }
        }
        return validWords;
    }
}



public class DictionartValidWordTest {

    @Test
    public void testValidWords() {
        Set<String> expectedSet = new HashSet<String>(Arrays.asList("awe", "is", "his", "awesome", "some", "this", "we"));
        assertEquals(expectedSet, DictionaryValidWords.findValidStrings("thisisawesome"));
    }
}

Answer 1

I only have one minor objection for the moment...

...

...

Why are you not using dependency injection??

OK, it turned out to be a major one. (I did consider using caps-lock!)

Consider a situation where you would want to do this operation for English words, and then for French words. Instead of using all things static, make a public constructor

private final Set<String> dictionary;

public DictionaryValidWords(Set<String> dictionary) {
    this.dictionary = dictionary;
}

You might consider this as "outside the core part of the code" but it's really not. And it is a very important change to make, class-design wise and best-practices wise.

You could then use a DictionaryFactory class where you could have methods (static or non-static, as you prefer), for exampleDictionary (your current dictionary), english, french, etc...

Answer 2

There's a potentially useful datastructure that goes by various names, but I first heard it called a 'Trie'. It might be worth a quick look, especially some of its variations such as the 'Patricia Trie', or Compact Prefix Tree.

Consider this toy example search phrase:

leaders

along with its corresponding dictionary,

lead leader leaders

If I stored the three words separately, that's a total of 17 characters. If I store them in a compact prefix tree, I only have to store 7 characters:

[lead] - [er] - [s]

Now have a quick think about the string matching process. In your current system, we would first try to match the word lead, which will take us 4 steps. Next we will try to match the word leader, taking an additional 6 steps, and finally leaders for 7 steps giving us a total of 17 character comparison operations (and three tree lookups).

With sensible use of a prefix tree, in the process of matching the longest word leaders, we will already have matched every word that is a prefix of leaders: lead and leader.

Now lets add another element to our tree, leaded. There's a new node, (e) which doesn't mark a word, so I've used parentheses instead of square brackets.

[lead] - (e) - [r] - [s]
            \ [d]

Now, when we walk through the tree and build up the prefix leade, we have two options for valid next characters, r and d. Because our search string is Leaders, we can't match leaded, but we can reject it right now without having to do a fresh search that will need to run 6 character comparisons.

There are some useful speedups to be had here. I couldn't tell you the computational complexity, but I'm pretty certain that a good compact prefix tree implementation will beat a brute-force hash-set dictionary search implementation in both time and memory used.

Answer 3

Efficiency

You're using a TreeSet to hold the valid words, but you're not using its key feature: ordering. As such, it would be more efficient to use a HashSet instead. That will give constant time lookups, as opposed to logarithmic time. (See this related discussion.)

The algorithm is definitely wasteful. If for example the longest word in the dictionary is 3 characters long and the input text is 50, the for loop will happily try all substrings, even if most of them will be longer than 3. As a small speed improvement you could pre-calculate the minimum and maximum word lengths when you create the dictionary, and include extra conditions in the for loop using those values.

Another improvement could be, if memory permits, to build a dictionary of all possible prefixes, with signature Map<Integer, Set<String>> where the key is the length of a prefix, mapped to the set of prefixes of that length. Then in the for loop, you could check if the current substring is contained in the prefix dictionary, otherwise break the innermost loop and continue from the next i + 1.

Probably there is a more elegant logic to solve this problem without a brute force approach but I can't think of it right now...

Remove unnecessary elements

You're not using the private constructor. So drop it.

This validation seems pointless:

if (str.length() ==  0) {
    throw new IllegalArgumentException("Strings of length 0 are illegal");
}

Without this, your method will still work fine, and return an empty set for an empty string input, which makes sense. So I think you can drop this.

Unit testing

Add more unit tests for all possible corner cases you can think of. For example empty string. Or string with words not in the dictionary. Each of these in a separate test case.