Find the longest word in the array consisting of other words in the array
I have an array of words and need to find the longest word in the array that consists of other words in that array. For example:
String[] mass = {
"five",
"fivetwo",
"fourfive",
"fourfivetwo",
"one",
"onefiveone",
"two",
"twofivefourone"
};
The result should be "fourfivetwo" → "fourfive" "two". Could you help me find the algorithm?
source to share
There is a solution using the KMP string matching algorithm and graphics.
Algorithm:
1) Iteration over words. Set each word for "main word", the word you want to build. Follow the steps below for each such word.
2) You have fixed one word, let's call it W. Now repeat all the words and run KPM, comparing them with W. Now you can plot the letters of the word W. Let's explain with an example:
W = "abacdeeee"
Other_word = ["aba", "cde", "eee"]
Word "aba" would connect letter 1 in word W to letter 4.
Word "cde" would connect 4 to 7.
Word "eee" would connect 7 to 9.
Each letter in W is node and other words will make edges.
If there exists a path between first and last letter, which you can
check using BFS/DFS, you can build word W out of other words.
3) Repeat the process for each word and choose the longest that can be created from the others.
Time complexity:
Suppose N is the number of words and L is the average length.
For one word, you run KMP with each word, which takes O (N * (L + L)). Worst case construction graph takes O (N ^ 2), same for BFS. For each word W, you waste O (NL + N ^ 2) worst case, but the number of edges will most likely be proportional to N, so the average is O (NL).
As you need above for each N, you get the result:
Worst difficulty: O (N ^ 2 * L + N ^ 3)
Average difficulty: O (N ^ 2 * L)
source to share
Thanks, I have already solved if anyone is interested in the code here. I'm ashamed of it, but it works
public class MyMap {
private Map<String, ArrayList<Pair>> map = new TreeMap<String, ArrayList<Pair>>();
private String[] key;
// create special map
//key = element our array
//value = pair elemene
// string = word which contains in this key
// int = count this word (which contains in this key)
public MyMap(String[] ArrayWord) {
key = ArrayWord;
//init arraylist
for (int i = 0; i < ArrayWord.length; i++) {
map.put(ArrayWord[i], new ArrayList<Pair>());
}
//find word which containing key
/*
example:
String[] mass = {
"f",
"five",
"fivetwo",
"one",
"onefiveone",
"two"
};
map[0] => f->[]
map[1] => five->[(f:1)]
map[2] => fivetwo->[(f:1)(five:1)(two:1)]
map[3] => one->[]
map[4] => onefiveone->[(f:1)(five:1)(one:2)]
map[5] => two->[]*/
for (int i = 0; i < ArrayWord.length; i++) {
for (int j = 0; j < ArrayWord.length; j++) {
if (i != j) {
int count = 0;
if (ArrayWord[i].contains(ArrayWord[j])) {
String str = ArrayWord[i];
// find count word which contains in this key
while (str.contains(ArrayWord[j])) {
str = str.replaceFirst(ArrayWord[j], "-");
count++;
}
Pair help = new Pair(ArrayWord[j], count);
map.get(ArrayWord[i]).add(help);
}
}
}
}
}
public String getCompoundWord() {
String word = "";
//check have we compound word or not
if (isHaveCompoundWords()) {
/*remove Unique Elements of the words are found*/
deleteContainingWord();
/* find index element*/
int index = findIndexCompoundWord();
//return -1 if we have no word which compound just with other words array
try {
word = key[findIndexCompoundWord()];
return word;
} catch (IndexOutOfBoundsException ex) {
System.out.println("Have no word which compound just with other words array");
}
} else {
return "Have no word which compound with other words array, just unique element";
}
return key[findIndexCompoundWord()];
}
private void deleteContainingWord() {
/*
update map
after procedure we would have map like this
String[] mass = {
"f",
"five",
"fivetwo",
"one",
"onefiveone",
"two"
};
map[0] => f->[]
map[1] => five->[(f:1)]
map[2] => fivetwo->[(f:1)(ive:1)(two:1)]
map[3] => one->[]
map[4] => onefiveone->[(f:1)(ive:1)(one:2)]
map[5] => two->[]
*/
for (int i = 0; i < map.size(); i++) {
if (map.get(key[i]).size() > 0) {
ArrayList<Pair> tmp = map.get(key[i]);
for (int j = tmp.size() - 1; j >= 0; j--) {
for (int k = tmp.size() - 1; k >= 0; k--) {
if (k != j) {
// if word contains other word2, remove part word
if (tmp.get(j).getName().contains(tmp.get(k).getName())) {
String s = tmp.get(j).getName().replace(tmp.get(k).getName(), "");
tmp.get(j).setName(s);
}
}
}
}
map.put(key[i], tmp);
}
}
}
private int findIndexCompoundWord() {
int indexMaxCompaneWord = -1;
int maxCompaneWordLenght = 0;
for (int i = 0; i < map.size(); i++) {
if (map.get(key[i]).size() > 0) {
ArrayList<Pair> tmp = map.get(key[i]);
int currentWordLenght = 0;
for (int j = 0; j < tmp.size(); j++) {
if (!tmp.get(j).getName().isEmpty()) {
currentWordLenght += tmp.get(j).getName().length() * tmp.get(j).getCount();
}
}
if (currentWordLenght == key[i].length()) {
if (maxCompaneWordLenght < currentWordLenght) {
maxCompaneWordLenght = currentWordLenght;
indexMaxCompaneWord = i;
}
}
}
}
return indexMaxCompaneWord;
}
private boolean isHaveCompoundWords() {
boolean isHaveCompoundWords = false;
for (int i = 0; i < map.size(); i++) {
if (map.get(key[i]).size() > 0) {
isHaveCompoundWords = true;
break;
}
}
return isHaveCompoundWords;
}
}
source to share