Design Efficient Multi-Level Access Control System

Scenario

Multi-level access control lists (country → city) must be queried quickly.

Question

Design and implement a permission system where each geographic path (e.g., /France/Paris) can be authorised. Support add(path) and check(path).

Hints

Use a trie whose nodes store ACL flags and wildcards.

Trie-Based Multi-Level ACL Matching

Design a permission matcher for geographic-like paths. You are given operations ops, each of form ["add", pattern] or ["check", path]. Paths and patterns are normalized strings starting with '/', composed of zero or more non-empty segments separated by '/'. A pattern authorizes any path it matches. Wildcards: (1) "*" matches exactly one segment; (2) "**" matches zero or more trailing segments and may appear only as the final segment of a pattern. For each "check" operation, return True if any previously added pattern matches the path, else False. Return the results as a list of booleans in the order of "check" operations.

Constraints

• 1 <= len(ops) <= 100000
• Each op is ["add", pattern] or ["check", path]
• Paths/patterns start with '/' and have segments separated by '/'
• Wildcard '*' matches exactly one segment
• Wildcard '**' matches zero or more trailing segments and may appear only as the final segment of a pattern
• No redundant slashes; segments are non-empty (root '/' has zero segments)
• Total length of all strings <= 1e6

Examples

Example 1

Input: ops = [["add","/France/Paris"],["check","/France/Paris"],["check","/France/Lyon"]]
Output: [True, False]

Explanation: Exact pattern '/France/Paris' authorizes only the same path.

Example 2

Input: ops = [["add","/France/*"],["add","/Spain/Madrid/**"],["check","/France/Paris"],["check","/Spain/Madrid/Center/Block"],["check","/Spain/Barcelona"]]
Output: [True, True, False]

Explanation: Pattern '/France/*' matches any single city in France; '/Spain/Madrid/**' matches Madrid and any deeper subpaths.

Hints

1. Build a trie keyed by path segments.
2. Mark nodes where a pattern ends (terminal) and where a pattern with trailing '**' ends (starstar).
3. During check, perform BFS/DFS over trie states (node, index), following exact and '*' edges; if you encounter starstar at any visited node, it's an immediate match.

Approach

Use a trie keyed by path segments. Each node keeps: (1) children for exact segment matches; (2) a single child for '' matching exactly one segment; (3) a terminal flag for patterns that end exactly at the node; (4) a starstar flag to represent a pattern that ends with '**', which matches any remainder. For checking, perform a BFS over states (node, index-in-path). From each state, if starstar is set, it matches immediately. Otherwise, if we've consumed all segments and terminal is set, it's a match. If not at the end, transition on the exact child for the current segment and on the '' child if it exists, advancing the index by one in both cases. A visited set over (node, index) prevents revisiting states. Adding a pattern walks/creates nodes along exact or '*' edges; encountering a final '**' sets the starstar flag at the current node.

• Time complexity: Add: O(S) where S is number of segments in the pattern; Check: O(K) on average (two possible edges per step, with visited pruning), worst-case O(K * W) with W <= 2.
• Space complexity: O(T) where T is the number of trie nodes, proportional to total unique segments across added patterns.