Problem 454248 · hard · Phase 04 Non-Linear Data Structures

Stock Codes by Their Bookends

trie · counts and deletions · key design · design · classes

A hardware shop labels its stock with short codes; several items may share a code. Staff often search by both ends of a code: "starts with bo and ends with lt". Design Catalogue:

  • Catalogue() starts empty.
  • add(code) stocks one more item with this code (returns None).
  • remove(code) removes one item with this code and returns True, or returns False if no item has it.
  • count(start, end) returns how many items currently in stock have a code that begins with start and ends with end. Either string may be empty (it then matches everything), and the two may overlap inside the code: "bolt" matches start = "bol", end = "olt".

Examples

ops:  ["Catalogue", "add", "add", "add", "add", "count", "count", "count", "remove", "count", "remove", "count"]
args: [[], ["bolt"], ["boot"], ["bolt"], ["belt"], ["bo", "t"], ["b", "lt"], ["bolt", "bolt"], ["bolt"], ["", "lt"], ["nut"], ["bol", "olt"]]
Output: [None, None, None, None, None, 3, 3, 2, True, 2, False, 1]
Explanation: "bo...t" matches bolt, boot, bolt. "b...lt" matches bolt, bolt, belt.
After one bolt is removed, bolt and belt end with "lt".

Constraints

  • Codes, start and end have length 0 .. 10 and use lowercase letters
  • Up to 2 * 10**4 calls in total
  • Target: count must not look at every stocked item; about O(L**2) per add or remove and O(L) per count is fine, where L is the code length

Goals

  • Answer a two-sided (start and end) filter with one walk down a trie
  • Insert every suffix of a word glued to the whole word so both ends become one path
  • Keep counts so that duplicates and removals stay correct
Starting Python…