⭐ 题目日期：

字节 - 2025/7/16

📝 题解：

为了高效存储10万个路径规则并快速判断一个请求路径是否匹配这些规则，可以采用分层存储和匹配策略。以下是完整的解决方案：

1. 规则分类存储

将路径规则分为三类存储，以优化不同匹配场景：

• 精确匹配规则（完全相等）：

  exact_match_rules = set()
  # 示例：exact_match_rules = {"/login", "/user/profile"}

• 前缀匹配规则（以...*结尾，匹配路径前缀）：

  prefix_trie = {}  # 字典实现的 Trie 树
  # 示例：规则 "/static/*" -> 存储为 "/static/"

• 后缀匹配规则（以*...开头，匹配路径后缀）：

  suffix_rules = {}  # 按后缀分组，键为后缀，值为规则列表
  # 示例：规则 "*.jpg" -> 存储为 {"jpg": ["*.jpg"]}

2. 规则添加逻辑

def add_rule(rule: str):
    if '*' not in rule:
        exact_match_rules.add(rule)
    elif rule.endswith('*'):
        # 前缀规则：去掉末尾 '*' 后插入 Trie
        prefix = rule[:-1]
        node = prefix_trie
        for char in prefix:
            node = node.setdefault(char, {})
        node['__end__'] = True  # 标记规则终点
    elif rule.startswith('*'):
        # 后缀规则：提取后缀并分组存储
        suffix = rule.split('.')[-1]  # 如 "*.jpg" -> "jpg"
        suffix_rules.setdefault(suffix, []).append(rule)

3. 路径匹配逻辑

def is_path_matched(path: str) -> bool:
    # 1. 检查精确匹配
    if path in exact_match_rules:
        return True

    # 2. 检查前缀匹配 (Trie 树)
    node = prefix_trie
    for char in path:
        if '__end__' in node:  # 当前路径前缀匹配成功
            return True
        if char not in node:
            break
        node = node[char]
    if '__end__' in node:  # 整个路径匹配前缀
        return True

    # 3. 检查后缀匹配
    if '.' in path:
        suffix = path.split('.')[-1]
        if suffix in suffix_rules:
            for rule in suffix_rules[suffix]:
                if path.endswith(rule[1:]):  # 去掉开头的 '*'
                    return True
    return False

4. 性能分析

• 精确匹配：哈希集合查找，时间复杂度 O(1)。
• 前缀匹配：Trie 树逐字符匹配，时间复杂度 O(k)（k为路径长度），与规则数量无关。
• 后缀匹配：按后缀分组后线性匹配，但每组规则数量少，实际接近 O(1)。

5. 优化扩展

• 内存优化：使用基数树（Radix Tree）合并公共前缀，减少 Trie 节点数。
• 复杂规则：如需支持正则表达式，单独存储并作为最后匹配层（但效率较低）。
• 并行匹配：对三类规则并行匹配，进一步加速。

示例测试

# 添加规则
add_rule("/login")          # 精确匹配
add_rule("/static/*")       # 前缀匹配
add_rule("*.jpg")           # 后缀匹配

# 测试路径
print(is_path_matched("/login"))         # True (精确匹配)
print(is_path_matched("/static/1.png")) # True (前缀匹配)
print(is_path_matched("/user/1.jpg"))   # True (后缀匹配)
print(is_path_matched("/unknown"))      # False

此方案在 10万规则下：

• 内存占用：约 100-200 MB（Trie 树占主导）。
• 匹配速度：单次请求 < 1毫秒（路径长度平均时）。

关键点：通过规则分类 + Trie 树 + 后缀分组，将全局匹配复杂度降至 O(路径长度)，避免遍历所有规则。