# [CC150v5] 18.7 Longest Word Made From Other Words

### Question

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.

### Code

public static void printLongestWord(String[] arr) {
Arrays.sort(arr, new LengthComparator());
HashSet<String> set = new HashSet<String>();
for (String str : arr) {
}
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;
}