Online Judge Solutions

Tuesday, December 9, 2014

Longest compound word

Question

copied from http://okckd.github.io/blog/2014/10/02/longest-word-made-from-other/
Given a list of words, write a program to find the longest word made of other words in the list.
EXAMPLE
Input: cat, banana, dog, nana, walk, walker, dogwalker
Output: dogwalker

Solution

Search it recursively from longest to shortest. Use HashSet to help us search for words quickly.
This question might look difficult at first, it’s actually a very classical recursive search.
public static void printLongestWord(String[] arr) {
    Arrays.sort(arr, new LengthComparator());
    HashSet<String> set = new HashSet<String>();
    for (String str : arr) {
        set.add(str);
    }
    for (String word : arr) {
        if (canDivide(word, 0, set)) {
            System.out.println(word);
            return;
        }
    }
    System.out.println("can not find such word");
}

private static boolean canDivide(String word, int from, HashSet<String> set) {
    if (from == word.length()) {
        return true;
    }
    for (int i = from; i < word.length(); i++) {
        String str = word.substring(from, i + 1);
        if (from == 0 && i == word.length() - 1) {
            continue;
        } else if (!set.contains(str)) {
            continue;
        }
        if (canDivide(word, i + 1, set)) {
            return true;
        }
    }
    return false;
}

3 comments:

  1. Can one word be used more than once? For example, input: dogdog, dog. Your solution will return true.

    ReplyDelete
    Replies
    1. This comment has been removed by the author.

      Delete
    2. Good question, here we assume it can be reused. We probably should clarify with the interviewer.

      Delete