Longest word made of other words in an array

Problem

Write a program to find the longest word made of other words.
EXAMPLE
Input: test, tester, testertest, testing, testingtester
Output: testingtester

Solution

1. This problem can be easily solved using a "Trie data structure"
2. First I sort the strings in descending order "Lengthwise", so longest string comes first.
3. Start with the first string and loop over sorted strings
4. Check if it can be made of other words by dividing strings into all possible combinations and doing same thing for each splits. So, whenever we find the word in the larger string, we delete the shorter word from the bigger word.
5. Retrun true if it is made of other strings and Save that string onto an array list.
6. Return the top string because that would be the longest string.
7. The size of array list will give you the total number of words that can be made of other words.

Java code

public static class LengthComparator implements Comparator<String> {
    public int compare(String o1, String o2) {
        if (o1.length() < o2.length())
            return 1;
        else if (o1.length() > o2.length())
            return -1;
        else
            return 0;
    }
}
 
public static String longestWordMadeOfOtherWords(String[] words) {
    Arrays.sort(words, new LengthComparator());
    for (String word : words) {
        String backup = new String(word);
        for (String otherWord : words) {
            if (!otherWord.equals(backup) && word.contains(otherWord)) {
                word = word.replace(otherWord, "");
            }
        }
        if (word.length() == 0)
            return backup;
    }
    return null;
}

Thanks.
References

• http://tianrunhe.wordpress.com/2012/06/10/longest-word-made-of-other-words-in-an-array/