检查列表中的字符串是否可以由相同列表中的元素拼接而成。

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], ....}

现在只需遍历原始列表并在映射中查找。如果找到，那么它就是可能的解之一。

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

- nagendra547

---

列表的大小是多少？ - TaQuangTu

它可能非常大。您可以考虑1 <= n <= 10000，其中n是列表的大小。 - nagendra547

你肯定需要一个递归解决方案。 - Vishwa Ratna

你需要所有的解决方案还是只需要第一个？ - Bentaye

所有的解决方案，包括2个字符串、3个字符串、4个字符串等等。 - nagendra547

Answer 1

我认为一种标准的方法可能是从字典中构建一个“trie”树。然后对于每个候选词，遍历这个“trie”树，并在匹配路径到达末尾（标记较小的单词）时，再次从“trie”树的顶部开始处理该候选词剩余的后缀。如果存在相似的匹配，则每个候选词可能需要进行几次回溯尝试；但在只有10,000个词的字典中，除非数据退化，这些回溯应该平均很少发生。

- גלעד ברקן

Answer 2

首先，对于我的糟糕英语表示歉意。

我有一个简单的方法，您可以尝试：

步骤1：按元素长度降序排序列表

步骤2：依次（从已排序列表的左侧到右侧）根据以下规则将元素添加到树中：

• 树的每个节点包含一个字符串，树的根节点不包含任何内容

• 每个父节点中的字符串包含其子节点中的字符串

步骤3：获取结果：如果节点中字符串长度等于其子节点中字符串长度之和，则获得预期结果。

- TaQuangTu

Answer 3

这是一种暴力方法。我们可以先列出原始术语的列表，然后对该列表进行双重迭代，以生成所有组合可能性。对于每个组合，如果它已经包含在原始列表中，我们将该组合打印到控制台上。

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

- Tim Biegeleisen

---

谢谢你的解决方案。然而，这个解决方案的时间复杂度是O(n* n * n)。你使用了两个循环（O(n* n)），然后在列表中搜索另一个O(n)，所以总共是O(n* n* n)。我的建议是O(n* n)的解决方案。 - nagendra547

@nagendra547 这段代码只检查一个字符串是否可以由另外两个字符串组成，不考虑三元组。 - TaQuangTu

@nagendra547 然后使用HashSet来查找每个可能的匹配项。这避免了在列表中进行搜索，但可能会使用更多的存储空间。 - Tim Biegeleisen

@nagendra547，你的解决方案复杂度应该是O(2^n)，而不是O(n^2)，因为你说过，“通过将它们连接在一起创建所有字符串的组合（2个字符串在一起，3个字符串在一起等等）”。 - גלעד ברקן

@TimBiegeleisen 是的，这是个公平的理由。HashSet 的解决方案与我的类似。 - nagendra547

@TaQuangTu 三元组也可以使用。甚至可以使用四个单词。我没有提到只能使用两个单词。 - nagendra547

Answer 4

1. 使用AC自动机将集合中的所有字符串都添加到其中。

2. 将集合中的所有字符串与自动机进行匹配并记录匹配点。

3. 使用动态规划将匹配点连接起来。

最坏情况下的时间复杂度：O(n*（长度之和）)

n 来自于 DP 过程中需要决定的多个长度选项。想象一下一个字符串集合 {a，aa，aaa，aaaa，...，a^n}。

在此学习 AC 自动机：link

- tigertang

---

为什么没有人评论我的答案？:( - tigertang

讨论暴力方法并假设数据集恰好符合您的要求是毫无意义的。 - tigertang

Answer 5

这是一个子集和问题。 标准解法是动态规划，但通常你会发现针对整数的解决方案：子集和算法

适用于此的改编代码大致如下：

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

- One Lyner

Answer 6

感谢分享这个有趣的练习。

使用Java 8+和Streams，这是迭代列表和处理小或大数据集的最佳方法。

请记住，您可以使用以下方法：

• inputList.stream() 将列表转换为流
• inputList.parallelStream() 如果您的列表不包含同步对象并且不调用任何同步方法（不允许并行处理）。

在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=[最佳, 指南], rockstar=[摇滚, 明星]}

- bdzzaid