我有一个单词数组,需要找到数组中最长的单词,该单词由该数组中的其他单词组成。例如:
String[] mass = {
"five",
"fivetwo",
"fourfive",
"fourfivetwo",
"one",
"onefiveone",
"two",
"twofivefourone"
};
结果应该是“fourfivetwo”->“fourfive”“two”。你能帮我找到算法吗?
最佳答案
存在使用字符串匹配算法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)
关于arrays - 查找数组中最长的单词,该单词由数组中的其他单词组成,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/30027590/