Given a list of words, write a program to find the longest word made of other words in the list.
Rather than simply looking up if the right side is in the array, we would recursively see if we can build the right side from the other elements in the array
http://www.shuati123.com/blog/2014/10/02/longest-word-made-from-other/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;
}public static String printLongestWord(String arr[]) {
HashMap<String, Boolean> map = new HashMap<String, Boolean>();
for (String str : arr) {
map.put(str, true);
}
Arrays.sort(arr, new LengthComparator()); // Sort by length
for (String s : arr) {
if (canBuildWord(s, true, map)) {
System.out.println(s);
return s;
}
}
return "";
}
public static boolean canBuildWord(String str, boolean isOriginalWord, HashMap<String, Boolean> map) {
if (map.containsKey(str) && !isOriginalWord) {
return map.get(str);
}
for (int i = 1; i < str.length(); i++) {
String left = str.substring(0, i);
String right = str.substring(i);
if (map.containsKey(left) && map.get(left) == true &&
canBuildWord(right, false, map)) {
return true;
}
}
map.put(str, false);
return false;
}
http://www.ardendertat.com/2012/06/15/programming-interview-questions-28-longest-compound-word/
We will use the trie data structure, also known as a prefix tree. Tries are space and time efficient structures for text storage and search. They let words to share prefixes.
The complexity of this algorithm is O(kN) where N is the number of words in the input list, and k the maximum number of words in a compound word. The number k may vary from one list to another, but it’ll generally be a constant number like 5 or 10. So, the algorithm is linear in number of words in the list, which is an optimal solution to the problem.
上述代码将单词存放在哈希表中，以得到O(1)的查找时间。排序需要用O(nlogn)的时间， 判断某个单词是否可以由其它单词组成平均需要O(d)的时间(d为单词长度)， 总共有n个单词，需要O(nd)的时间。所以时间复杂度为：O(nlogn + nd)。 n比较小时，时间复杂度可以认为是O(nd)；n比较大时，时间复杂度可以认为是O(nlogn)。
Hash hash;
inline bool cmp(string s1, string s2){//按长度从大到小排
return s2.length() < s1.length();
}
bool MakeOfWords(string word, int length){
//cout<<"curr: "<<word<<endl;
int len = word.length();
//cout<<"len:"<<len<<endl;
if(len == 0) return true;
for(int i=1; i<=len; ++i){
if(i == length) return false;//取到原始串，即自身
string str = word.substr(0, i);
//cout<<str<<endl;
if(hash.find((char*)&str[0])){
if(MakeOfWords(word.substr(i), length))
return true;
}
}
return false;
}
void PrintLongestWord(string word[], int n){
for(int i=0; i<n; ++i)
hash.insert((char*)&word[i][0]);
sort(word, word+n, cmp);
for(int i=0; i<n; ++i){
if(MakeOfWords(word[i], word[i].length())){
cout<<"Longest Word: "<<word[i]<<endl;
return;
}
}
}http://stackoverflow.com/questions/32984927/find-the-longest-word-made-of-other-words
Answering your question indirectly, I believe the following is an efficient way to solve this problem using tries.
Build a trie from all of the words in your string.
Sort the words so that the longest word comes first.
Now, for each word W, start at the top of the trie and begin following the word down the tree one letter at a time using letters from the word you are testing.
Each time a word ends, recursively re-enter the trie from the top making a note that you have "branched". If you run out of letters at the end of the word and have branched, you've found a compound word and, because the words were sorted, this is the longest compound word.
If the letters stop matching at any point, or you run out and are not at the end of the word, just back track to wherever it was that you branched and keep plugging along.
#!/usr/bin/env python3
#End of word symbol
_end = '_end_'
#Make a trie out of nested HashMap, UnorderedMap, dict structures
def MakeTrie(words):
root = dict()
for word in words:
current_dict = root
for letter in word:
current_dict = current_dict.setdefault(letter, {})
current_dict[_end] = _end
return root
def LongestCompoundWord(original_trie, trie, word, level=0):
first_letter = word[0]
if not first_letter in trie:
return False
if len(word)==1 and _end in trie[first_letter]:
return level>0
if _end in trie[first_letter] and LongestCompoundWord(original_trie, original_trie, word[1:], level+1):
return True
return LongestCompoundWord(original_trie, trie[first_letter], word[1:], level)
#Words that were in your question
words = ['test','testing','tester','teste', 'testingtester', 'testingtestm', 'testtest','testingtest']
trie = MakeTrie(words)
#Sort words in order of decreasing length
words = sorted(words, key=lambda x: len(x), reverse=True)
for word in words:
if LongestCompoundWord(trie,trie,word):
print("Longest compound word was '{0:}'".format(word))
break