优化二维字符串列表匹配算法：将时间复杂度降至O(n²)以下

给定两个List<List<String>>（记为a和b），需返回Map<List<String>, List<List<String>>>，规则如下：

• 将a的元素记为a1、a2、a3……，b的元素记为b1、b2、b3……
• 筛选出a中与b1存在字符串重叠的元素
• 结果中以b1为键，符合条件的a元素列表为值

示例 #

定义a = [[a, b, c], [d, e, f], [a, d, f]]，b = [[a, d], [a], [c], [x]]
返回结果：

实际场景中a和b的列表长度均超过100000，原代码使用List.contains实现，最坏时间复杂度为O(n³)，需要优化到O(n²)以下。

原Java代码 #

public Map<List<String>, List<List<String>>> compute(List<List<String>> a, List<List<String>> b) {
    Map<List<String>, List<List<String>>> result = new HashMap<>();
    for (List<String> elem : b) {
        result.put(elem, a.stream().filter(e -> e.stream().anyMatch(elem::contains)).toList());
    }
    return result;
}

优化方案 #

核心思路

通过预构建字符串到a中对应列表的映射，将原逻辑中“遍历b元素→遍历a元素逐一检查重叠”的嵌套操作，改为“先缓存a中所有字符串关联的列表，再通过b元素的字符串直接查询映射”，彻底避免对a的重复遍历。

优化后的Java代码

import java.util.*;

public class ListMatcher {
    public Map<List<String>, List<List<String>>> compute(List<List<String>> a, List<List<String>> b) {
        // 预构建：字符串 → 包含该字符串的a列表集合（用Set避免重复存储同一列表）
        Map<String, Set<List<String>>> stringToALists = new HashMap<>();
        for (List<String> aList : a) {
            for (String s : aList) {
                stringToALists.computeIfAbsent(s, k -> new HashSet<>()).add(aList);
            }
        }

        Map<List<String>, List<List<String>>> result = new HashMap<>();
        for (List<String> bElem : b) {
            Set<List<String>> matchedLists = new HashSet<>();
            for (String s : bElem) {
                Set<List<String>> relatedLists = stringToALists.get(s);
                if (relatedLists != null) {
                    matchedLists.addAll(relatedLists);
                }
            }
            // 转成List保持结果格式一致
            result.put(bElem, new ArrayList<>(matchedLists));
        }
        return result;
    }
}

复杂度分析

• 预处理阶段：遍历a的所有元素，时间复杂度为O(M*K)，其中M是a的列表数量，K是每个a列表的平均字符串数。
• 处理b阶段：遍历b的所有元素，每个b元素的字符串数为L，查询映射的时间为O(1)，合并集合的时间取决于匹配的列表数量，整体最坏时间复杂度为O(N*L + T)，其中N是b的列表数量，T是所有匹配的a列表总次数。
• 整体复杂度远低于O(n²)，实际场景下效率会有数量级提升，彻底避免了原方案中对a的重复嵌套遍历。

注意事项

• Java中ArrayList的equals和hashCode基于元素顺序和内容实现，因此可以直接作为HashMap的键使用。
• 若a中存在完全相同的列表，HashSet会自动去重；若需保留重复列表，可将Set替换为List并处理重复添加逻辑（通常a中列表为唯一元素）。

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