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

Solution

from typing import List
from collections import deque

class _Node:
    __slots__ = ("children", "star_child", "terminal", "starstar")
    def __init__(self) -> None:
        self.children = {}          # type: dict[str, _Node]
        self.star_child = None      # type: _Node | None
        self.terminal = False       # exact pattern ends here
        self.starstar = False       # pattern with trailing '**' ends here


def process_acl_operations(ops: List[List[str]]) -> List[bool]:
    root = _Node()

    def _split(path: str) -> List[str]:
        # Returns list of non-empty segments; '/' -> []
        return [seg for seg in path.split('/') if seg]

    def add(pattern: str) -> None:
        node = root
        parts = _split(pattern)
        for i, seg in enumerate(parts):
            if seg == "**":
                # Per constraints, '**' appears only as the final segment.
                node.starstar = True
                return
            elif seg == "*":
                if node.star_child is None:
                    node.star_child = _Node()
                node = node.star_child
            else:
                nxt = node.children.get(seg)
                if nxt is None:
                    nxt = _Node()
                    node.children[seg] = nxt
                node = nxt
        node.terminal = True

    def check(path: str) -> bool:
        parts = _split(path)
        q = deque([(root, 0)])
        visited = set()  # set[tuple[int, int]] of (node_id, index)
        while q:
            node, i = q.popleft()
            key = (id(node), i)
            if key in visited:
                continue
            visited.add(key)

            # '**' matches any remaining segments (including zero)
            if node.starstar:
                return True

            if i == len(parts):
                if node.terminal:
                    return True
                continue

            seg = parts[i]
            if node.star_child is not None:
                q.append((node.star_child, i + 1))
            child = node.children.get(seg)
            if child is not None:
                q.append((child, i + 1))
        return False

    out: List[bool] = []
    for op, arg in ops:
        if op == "add":
            add(arg)
        elif op == "check":
            out.append(check(arg))
        else:
            # Inputs are guaranteed valid per constraints
            pass
    return out