我有一个单词数组，需要找到由该数组中其他单词组成的最长单词。例如：
String[] mass = {
"five",
"fivetwo",
"fourfive",
"fourfivetwo",
"one",
"onefiveone",
"two",
"twofivefourone"
};
有一种解决方案是使用字符串匹配算法KMP和图形。
算法：
1）遍历单词。将每个单词设置为“主要单词”，即您想要构建的单词。对于每个这样的单词，执行以下步骤。
2）您固定了一个单词，让我们称其为W。现在再次遍历所有单词，并运行KPM将它们与W进行比较。现在，您可以在单词W的字母上构建图形。让我们通过示例来解释：
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) 重复上述过程，对于每个单词选择可以由其他单词组成的最长单词。
时间复杂度：
假设N是单词数，L是平均长度。
对于每个单词，您需要使用KMP算法与其他单词进行比较，这将花费O(N * (L + L))的时间。构建图形在最坏情况下需要O(N^2)，BFS同样如此。 对于每个单词W，您最多需要花费O(NL + N^2)的时间，但是边的数量很可能与N成比例，因此平均时间复杂度为O(NL)。
由于您需要对每个N执行上述操作，因此得出以下结果：
最坏时间复杂度：O(N^2*L + N^3)
平均时间复杂度：O(N^2*L)
谢谢大家，我已经决定了，如果有人感兴趣，这里是代码。虽然不太好意思，但它确实可以运行。
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;
}
}