java - 检查列表中的字符串是否可以通过连接同一列表中的元素形成

Question

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

例如:

输入列表 -

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

输出:-

rockstar -> rock, star

bestguide -> best, guide

这里的“rockstar”可以用rock和star组成。类似地，“bestguide”可以通过连接“best”和“guide”来形成。

到目前为止我已经有了解决方案 - 通过相互连接来创建字符串的所有组合(2 个字符串在一起，3 个字符串在一起等等)并存储在 Map 中。

map 结构如下

Map<String, List<String>>

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

现在检查只需遍历原始列表并检查 map 。如果找到了，那么这就是可能的解决方案之一。

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

Answer 1

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