[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) {
		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;
}