The callsign register

A gliding club's radio room keeps a register of callsigns. The controller hears them one character at a time and cannot wait for a search of the whole file.

The problem

Build the register. Three instructions arrive one at a time:

• ("register", callsign) — add a callsign to the file. Registering one twice changes nothing. This instruction reports nothing.
• ("listed", text) — report whether that exact callsign is on file.
• ("prefix", text) — report whether any callsign on file starts with that text. A callsign counts as a prefix of itself.

Input. ops — a list of instruction tuples in the shapes above.

Output. A list of booleans, one per listed and per prefix, in order.

Example.

[("register", "GKAT"), ("listed", "GKAT"), ("listed", "GKA"),
 ("prefix", "GKA"), ("prefix", "GKAT"), ("prefix", "GKB")]
  ->  [True, False, True, True, False]

GKA is three characters the controller has heard so far, so something on file starts that way — but nobody flies under GKA, so it is not listed.

A second example, where one callsign is a prefix of another:

[("register", "MRP7"), ("register", "MR"), ("listed", "MR"),
 ("listed", "MRP7"), ("listed", "MRP"), ("prefix", "MRP")]
  ->  [True, True, False, True]

Registering MR after MRP7 must not disturb the longer callsign, and MRP is still only a partial hearing.

Constraints.

• 1 <= len(ops) <= 10^5
• A callsign is 1 to 8 characters, uppercase letters and digits only.
• The characters across all instructions total at most 10⁶.

Hints

Approach

Brute force

Keep the callsigns in a set. listed is then a hash lookup, but prefix has to compare the text against every callsign on file: 10⁵ queries over a register of 10⁵ callsigns is 10¹⁰ character comparisons.

The insight

Store the callsigns as a tree of characters, one node per distinct prefix. Both questions become a walk of at most eight edges, and neither depends on how many callsigns are on file.

The tree holds every prefix of every stored callsign as a path, because that is how insertion builds it — character by character from the root. So prefix is exactly the question "does this path exist?". listed is a different question, and the tree cannot answer it from the path alone: GKA is a path but not a callsign. That is what the end marker is for — one flag per node, set only where a registered callsign stops.

Algorithm

1. The register is a node whose children are keyed by character.
2. To register, walk the characters from the root, creating a child node for any character that has none, then set the end marker on the final node.
3. To walk a query, follow one child per character; if a character has no child, the path does not exist.
4. prefix reports whether the walk finished.
5. listed reports whether the walk finished and the node it landed on carries the end marker.

Complexity

Time O(L) per instruction, where L is the length of that callsign — at most eight steps here, whatever the register holds. Space O(C) for C characters registered, one node per distinct prefix.

Solution

"""Callsign register — a prefix tree where each edge is one character."""

# A callsign is letters and digits only, so None can never be a real edge and is
# safe as the marker for "a callsign ends at this node".
END = None


def walk(node, text):
    """The node reached by spelling out `text`, or None if the path runs out."""
    for ch in text:
        node = node.get(ch)
        if node is None:
            return None
    return node


def solve(ops):
    root = {}
    answers = []

    for op in ops:
        move, text = op[0], op[1]
        if move == "register":
            node = root
            for ch in text:
                node = node.setdefault(ch, {})   # one node per distinct prefix
            node[END] = True
        elif move == "listed":
            node = walk(root, text)
            answers.append(node is not None and END in node)
        else:                                    # ("prefix", text)
            answers.append(walk(root, text) is not None)

    return answers

TESTS = [
    # A prefix of a registered callsign is not itself registered.
    (
        (
            [
                ("register", "GKAT"),
                ("listed", "GKAT"), ("listed", "GKA"),
                ("prefix", "GKA"), ("prefix", "GKAT"), ("prefix", "GKB"),
            ],
        ),
        [True, False, True, True, False],
    ),
    # Registering a callsign that is a prefix of an existing one marks the
    # node already on the path; both must stay listed.
    (
        (
            [
                ("register", "MRP7"), ("register", "MR"),
                ("listed", "MR"), ("listed", "MRP7"), ("listed", "MRP"),
                ("prefix", "MRP"),
            ],
        ),
        [True, True, False, True],
    ),
    # Nothing registered yet: every query is false, including the shortest one.
    (
        ([("listed", "ZQ"), ("prefix", "Z")],),
        [False, False],
    ),
    # A query longer than anything on file must not walk past the end.
    (
        (
            [
                ("register", "AB"),
                ("listed", "ABCDEFGH"), ("prefix", "ABC"), ("prefix", "AB"),
            ],
        ),
        [False, False, True],
    ),
    # Registering the same callsign twice is idempotent.
    (
        (
            [
                ("register", "N4X"), ("register", "N4X"), ("register", "N4XL"),
                ("listed", "N4X"), ("listed", "N4XL"), ("prefix", "N4XL"),
            ],
        ),
        [True, True, True],
    ),
]

Pitfalls

• Leaving out the end marker. listed("GKA") then reports True because the path exists on the way to GKAT, and the radio room calls an aircraft that does not exist.
• Overwriting a node while registering. Assigning a fresh empty node for each character, rather than reusing the child that is already there, erases MRP7 when MR is registered afterwards.
• Defaulting a missing child to an empty node. The walk then never fails, so prefix("ABC") reports True with only AB on file.

Variants

• Rollout rewind — another index shaped by the query it serves, keyed by minute rather than by character.