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

Question

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

例如：

输入清单-

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

输出：-

rockstar -> rock, star

bestguide -> best, guide

在这里，“摇滚明星”可以使用摇滚明星来形成。类似地，“最佳指南”可以通过结合“最佳”和“指南”来形成。

到目前为止，我的解决方案是-通过相互连接（2个字符串在一起，3个字符串等等）创建字符串的所有组合，并将其存储在Map中。

地图结构可能如下

Map<String, List<String>>

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

现在，仅检查原始列表并检查地图。如果找到了，那么它可能是解决方案之一。

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

Answer 1

这是暴力方法。我们可以首先形成原始术语的列表，然后双重迭代该列表以生成所有组合可能性。对于也已包含在原始列表中的每个组合，我们将该组合打印到控制台。

String[] terms = new String[] { "best",  "rockstar",   "star",  "guide",  "bestguide", "rock" };
List<String> list = Arrays.asList(terms);
Set<String> set = new HashSet<String>(list);
for (int i=0; i < list.size()-1; ++i) {
    for (int j=i+1; j < list.size(); ++j) {
        if (set.contains(list.get(i) + list.get(j))) {
            System.out.println(list.get(i) + list.get(j) + " -> " + list.get(i) + ", " + list.get(j));
        }
        if (set.contains(list.get(j) + list.get(i))) {
            System.out.println(list.get(j) + list.get(i) + " -> " + list.get(j) + ", " + list.get(i));
        }
    }
}

这打印：

bestguide -> best, guide
rockstar -> rock, star