如何获取不同长度List<String>的最长公共子串？能否一行实现？

核心思路 #

最长公共子串的长度不可能超过列表中最短的字符串，因此可以以最短字符串为基础，枚举其所有可能的子串，按长度从长到短排序后，找到第一个被所有字符串包含的子串，即为所求。

一行代码实现（无显式for循环） #

List<String> myStringArray = List.of("xxxyyy", "xxxyyy", "yyy");
String longestCommonSubstring = myStringArray.stream().min(Comparator.comparingInt(String::length)).map(shortest -> IntStream.range(0, shortest.length()).boxed().flatMap(start -> IntStream.rangeClosed(start + 1, shortest.length()).mapToObj(end -> shortest.substring(start, end))).distinct().sorted(Comparator.comparingInt(String::length).reversed()).filter(sub -> myStringArray.stream().allMatch(s -> s.contains(sub))).findFirst().orElse("")).orElse("");
System.out.println("The Longest Common Sub String = " + longestCommonSubstring);

代码说明 #

• 获取最短字符串：通过min(Comparator.comparingInt(String::length))拿到列表中最短的字符串，避免生成超出范围的无效子串。
• 生成所有子串：用IntStream遍历所有起始索引，再对每个起始索引遍历结束索引，通过substring(start, end)生成所有可能的子串。
• 去重与排序：distinct()去除重复子串减少判断次数，sorted(Comparator.comparingInt(String::length).reversed())按子串长度降序排列，确保第一个匹配的就是最长子串。
• 匹配校验：filter(sub -> myStringArray.stream().allMatch(s -> s.contains(sub)))检查当前子串是否被所有字符串包含，findFirst()直接拿到符合条件的最长子串。
• 边界处理：orElse("")处理列表为空或无公共子串的情况。

原代码的局限性 #

原代码通过按索引逐个比对字符的方式，仅适用于所有字符串长度相同且公共子串是索引对齐的连续字符序列的场景。当字符串长度不同时，索引会超出短字符串的范围导致报错，同时无法处理非索引对齐的公共子串（比如示例中的yyy，在长字符串中是末尾部分，原代码的索引比对逻辑无法识别）。

内容的提问来源于stack exchange，提问作者Raoul Duke