A nested set is written as a Python list. Each element is either a string (an atom) or another nested set, to any depth. Because these are sets:
- order never matters, at any level:
["a", ["b", "c"]]equals[["c", "b"], "a"]; - repeats don't matter either:
["a", "a", ["b"]]equals[["b", "b"], "a"].
An atom is never equal to a set, even a one-element one: "a" differs from ["a"], and [] differs from [[]].
Implement:
def nested_equal(a: list, b: list) -> bool
Return whether a and b describe the same set. Don't modify the inputs.
nested_equal(["pin", ["board", "user"]], [["user", "board"], "pin"]) # True
nested_equal(["x", "x", []], [[], "x"]) # True
nested_equal([["x"]], [["x"], "x"]) # False
nested_equal([[]], []) # False
nested_equal([["a", ["b"]]], [["a", "b"]]) # False
Constraints: up to 200,000 atoms and lists in total across both inputs, and nesting up to 5,000 levels deep, so a plain recursive walk hits Python's default recursion limit (raise it, or walk with an explicit stack).
Matching each element of one list against every element of the other (and recursing) is far too slow on wide inputs. Aim for roughly linear time in the total size.
Show hint
give every sub-set a canonical key that is the same for equal sets and different otherwise, then compare keys. Working bottom-up, a set's key can be built from its children's keys; an order-free, repeat-free container of them (or a small integer id per distinct key) does the job.