检查列表中的字符串是否可以由同一列表中的元素串联形成
例如：
输入列表-
{ best,rockstar,star,guide,bestguide,rock }
输出：-
rockstar -> rock,star
bestguide -> best,guide
这里的“摇滚明星”可以用摇滚明星组成。同样，可以通过将“最佳”和“指南”结合起来形成“最佳指南”。
到目前为止，我的解决方案是-通过相互连接来创建所有字符串组合（2个字符串在一起，3个字符串等等）并存储在Map中。
地图结构可能如下
Map<String,List<String>>
{rockstar : [rock,star],....}
现在检查仅遍历原始列表并检入地图。如果找到了，那么它可能是解决方案之一。
寻找具有更好的时间/空间复杂性的更好的解决方案
我认为一种标准的方法可能是从字典中构造一个trie。然后，对于每个候选者，遍历树桩，当匹配路径到达末尾（标记一个较小的单词）时，再次从树桩顶部继续，并保留候选者的其余后缀。如果存在相似的匹配项，我们可能需要对每个候选人进行一些回溯试验；但是在只有10,000个的字典中，除非数据退化，否则希望平均它们应该很少。
,首先，对不起我的英语不好。 我有一个幼稚的方法，您应该尝试一下：
第1步：以元素长度的降序对列表进行排序
第2步：依次（从排序列表的左到右），按照以下规则将元素逐一添加到树中：
树的每个节点都包含一个字符串，树的根没有任何内容
字符串在其子节点中都包含字符串。
这是蛮力方法。我们可以首先形成原始术语的列表，然后再次重复该列表以生成所有组合可能性。对于同样已经包含在原始列表中的每个组合，我们将该组合打印到控制台。
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
使用AC自动化，并将集合中的所有字符串添加到其中。
用自动化和记录匹配点匹配集合中的所有字符串。
使用动态编程来连接匹配点。
最坏情况下的时间复杂度：O（n *（长度之和））
n来自多个长度选项，具体取决于DP流程。想象一个字符串集{a，aa，aaa，aaaa，...，a ^ n}。
在此处了解交流自动化：link
,这是一个子集和问题。 标准解决方案是动态编程，但是通常您会找到整数的解决方案：Subset Sum algorithm
在此处进行调整将得到以下内容：
static List<String> substrings(String s) {
List<String> l = new ArrayList<String>();
for(int end=1; end < s.length()+1; ++end) {
for(int start=0; start < end; ++start) {
l.add(s.substring(start,end));
}
}
return l;
}
static boolean isInConcatenations(String target,List<String> list) {
Set<String> set = new HashSet<String>();
List<String> ss = substrings(target);
set.add("");
for (String s: list) {
if (s == target) continue; // do not use directly 'target' if it's in the list
Set<String> prev = Set.copyOf(set);
for (String sub: ss) {
if ((sub.startsWith(s) && prev.contains(sub.substring(s.length(),sub.length()))) ||
(sub.endsWith(s) && prev.contains(sub.substring(0,sub.length()-s.length()))) ) {
set.add(sub);
}
}
}
return set.contains(target);
}
这里substrings(s)返回一个字符串的所有非空子字符串的List。
复杂度大致为length(list) * length(target)**2
感谢您分享这个有趣的练习。
使用Java 8+和Streams，这是迭代列表和处理小型或大型数据集的最佳方法。
请记住，您可以使用以下方法：
在DZone上有一篇不错的文章可以了解Stream API的性能 https://dzone.com/articles/java-performance-for-looping-vs-streaming
final String input = "best,rockstar,star,guide,bestguide,rock,fake,rockfaller";
// Start to finding input pairs
List<String> inputList = Arrays.asList(input.split(","));
List<String> combi = inputList.stream()
.filter(s -> input.contains(s) && input.lastIndexOf(s) != input.indexOf(s))
.collect(Collectors.toList());
// Build ouput
final HashMap<String,List<String>> output = new HashMap<>();
inputList.stream()
// Remove pair words
.filter(s -> !combi.contains(s))
.filter(s -> combi.stream().anyMatch(pair -> s.startsWith(pair) || s.endsWith(pair)) )
.forEach( s -> {
List<String> result = combi.stream()
.filter(pair -> s.startsWith(pair) || s.endsWith(pair))
// Sort the output result
.sorted((s1,s2) -> s.startsWith(s1) ? 0 : 1)
.collect(Collectors.toList());
Collections.sort(result);
if(result.size() > 1)
{
output.put(s,result);
}
});
System.out.println(output);
这是打印HashMap结果时的输出
{bestguide = [best，guide]，rockstar = [rock，star]}