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.EXAMPLEInput: cat, banana, dog, nana, walk, walker, dogwalkerOutput: 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;
}
Can one word be used more than once? For example, input: dogdog, dog. Your solution will return true.
ReplyDeleteThis comment has been removed by the author.
DeleteGood question, here we assume it can be reused. We probably should clarify with the interviewer.
Delete