1 需求背景

双轨成色配置，可以按照适用范围配置。每个适用范围都由“品类”、“品牌”、“型号”组成，其中品类必填，品牌和型号非必填，当品牌不为空时型号非必填。

要求不同的适用范围互斥，不能有交集（从左至右）。

	有交集
{1, 10}	true
{1, 10}	false
{1, 10, 101}	false

2 实现思路

2.1 适用范围实体定义

@Data
@Builder
@NoArgsConstructor
@AllArgsConstructor
public static class PgScope {
    private Integer cateId;
    private Integer brandId;
    private Integer modelId;
}

2.2 简单明了求列表公共前缀

/**
 * 适用范围是否有重叠
 */
public static boolean checkIntersection(List<PgScope> scopeList) {
    List<List<Integer>> list = new ArrayList<>();
    for (PgScope pgScope : scopeList) {
        // 过滤 null 值
        List<Integer> path = Lists.newArrayList(pgScope.getCateId(), pgScope.getBrandId(), pgScope.getModelId())
                .stream().filter(Objects::nonNull).collect(Collectors.toList());
        for (List<Integer> tmp : list) {
            if (checkIntersection(tmp, path)) {
                return true;
            }
        }
        list.add(path);
    }
    return false;
}

public static boolean checkIntersection(List<Integer> path1, List<Integer> path2) {
    int minLength = Math.min(path1.size(), path2.size());
    for (int i = 0; i < minLength; i++) {
        if (!Objects.equals(path1.get(i), path2.get(i))) {
            // 发现同一位置两个列表元素不一样，即返回没有交集
            return false;
        }
    }
    // 存在公共前缀，返回有交集
    return true;
}

设定范围数量为 n，路径长度为 k，该算法时间复杂度为 O(kn²)

该场景 k 最大为 3，时间复杂度简化为 O(n²)

2.3 来点操作 Trie树

参考：DFA敏感词过滤算法

下面图示下建立 Trie 树的过程

添加

添加 {1, 10}，因为 Trie 数中已存在 {1, 10} 路径，所以无法添加成功

添加 

@Data
public static class TrieNode {
    /**
     * 路径结束标识
     */
    private Boolean end = false;
    /**
     * 子节点
     */
    private Map<Integer, TrieNode> children = new HashMap<>();
}

/**
 * 范围是否有重叠
 */
public static boolean checkIntersection(List<PgScope> scopeList) {
    TrieNode root = new TrieNode();
    for (PgScope pgScope : scopeList) {
        List<Integer> path = Lists.newArrayList(pgScope.getCateId(), pgScope.getBrandId(), pgScope.getModelId())
                .stream().filter(Objects::nonNull).collect(Collectors.toList());
        if (hit(root, path, 0)) {
            return true;
        }
        add(root, path, 0);
    }
    return false;
}

/**
 * 递归匹配当前节点，是否存在子节点与之有交集
 *
 * @param node 前缀树节点
 * @param path 待匹配路径
 * @param index 路径位置下标
 * @return 是否有交集
 */
public static boolean hit(TrieNode node, List<Integer> path, int index) {
    if (index >= path.size()) {
        return false;
    }
    Integer key = path.get(index);
    TrieNode child = node.getChildren().get(key);
    if (Objects.isNull(child)) {
        return false;
    }
    // 当前路径终点，或者是前缀树结束标识，表明与之有交集
    if (index == path.size() - 1 || child.getEnd()) {
        return true;
    }
    return hit(child, path, index + 1);
}

/**
 * 递归添加到前缀树中
 */
public static void add(TrieNode node, List<Integer> path, int index) {
    if (index >= path.size()) {
        return;
    }
    Integer key = path.get(index);
    TrieNode child = node.getChildren().get(key);
    if (Objects.isNull(child)) {
        // 如果不存在需要新建节点挂上去
        child = new TrieNode();
        node.getChildren().put(key, child);
    }
    if (index == path.size() - 1) {
        child.end = true;
    }
    add(child, path, index + 1);
}

设定范围数量为 n，路径长度为 k，该算法时间复杂度为 O(kn)

该场景 k 最大为 3，时间复杂度简化为 O(n)

验证代码

public static void main(String[] args) {
    PgScope scope1 = PgScope.builder()
            .cateId(1)
            .brandId(10)
            .build();
    PgScope scope2 = PgScope.builder()
            .cateId(1)
            .brandId(10)
            .modelId(101)
            .build();
    PgScope scope3 = PgScope.builder()
            .cateId(1)
            .brandId(11)
            .modelId(110)
            .build();
    // {1, 10}
    // {1, 10, 101}
    // true
    System.out.println(checkIntersection(Lists.newArrayList(scope1, scope2)));
    // {1, 10}
    // {1, 11, 110}
    // false
    System.out.println(checkIntersection(Lists.newArrayList(scope1, scope3)));
    // {1, 10, 101}
    // {1, 11, 110}
    // false
    System.out.println(checkIntersection(Lists.newArrayList(scope2, scope3)));
}