arrays - 查找数组中最长的单词，该单词由数组中的其他单词组成

Question

我有一个单词数组，需要找到数组中最长的单词，该单词由该数组中的其他单词组成。例如:

  String[] mass = {
            "five",
            "fivetwo",
            "fourfive",
            "fourfivetwo",
            "one",
            "onefiveone",
            "two",
            "twofivefourone"
        };

结果应该是“fourfivetwo”->“fourfive”“two”。你能帮我找到算法吗？

Answer 1

存在使用字符串匹配算法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)