java - 检查列表中的字符串是否可以由同一列表中的元素串联形成

Question

检查列表中的字符串是否可以由同一列表中的元素串联形成

例如：

输入列表 -

{ best,  rockstar,   star,  guide,  bestguide, rock }

输出 ：-

rockstar -> rock, star

bestguide -> best, guide

在这里，“摇滚明星”可以用摇滚和明星组成。类似地，“bestguide”可以通过连接“best”和“guide”来形成。

到目前为止我的解决方案 - 通过相互连接创建所有字符串组合（2 个字符串在一起，3 个字符串在一起，依此类推）并存储在地图中。

地图结构可以如下

Map<String, List<String>>

{rockstar : [rock, star], ....}

现在检查只是遍历原始列表并检查地图。如果找到它，那么它是一种可能的解决方案。

寻找具有更好时间/空间复杂度的更好解决方案

标签： javaarraysstringalgorithm

Answer 1

我认为一种标准方法可能是从字典中构造一个 trie。然后对于每个候选者，遍历特里树，当匹配路径到达末尾（标记一个较小的单词）时，再次从特里树的顶部继续使用候选者的剩余后缀。如果存在类似匹配，我们可能需要对每个候选人进行几次回溯试验；但是在只有 10,000 个的字典中，除非数据是退化的，否则这些平均应该很少。