Reconstructing Sequence

Prereq: Topological Sort

A sequence is a list of integers.

We are given an original sequence and a list of subsequences seqs.

Determine whether original is the only sequence that can be reconstructed from seqs. Reconstruction means building the shortest sequence so that all sequences in seqs are subsequences of it.

Parameters

  • original: a list of integers of size n representing the original sequence.
  • seqs: a list of sequences of size m representing the sequences to be reconstructed.

Result

  • true or false, depending on whether the original sequence can be uniquely reconstructed.

Examples

Example 1:

Input: original: [1,2,3], seqs: [[1,2], [1,3]]

Output: false

Explanation:

[1,2,3] is not the only one sequence that can be reconstructed, because [1,3,2] is also a valid sequence that can be reconstructed.

Example 2:

Input: original: [1,2,3], seqs: [[1,2]]

Output: false

Explanation:

There is only one subsequence, so the reconstructed original sequence can only be [1,2] which is missing 3.

Example 3:

Input: orginal: [1,2,3], seqs: [[1,2], [1,3], [2,3]]

Output: true

Explanation:

[1,2,3] is the only sequence that can be reconstructed from [1,2], [1,3], and [2,3].

Example 4:

Input: original: [4,1,5,2,6,3], seqs: [[5,2,6,3], [4,1,5,2]]

Output: true

Explanation:

[4,1,5,2,6,3] is the only sequence that can be reconstructed from [[5,2,6,3], [4,1,5,2]].

Constraints

  • 1 <= n <= 10^4
  • 1 <= m <= 10^4
  • 1 <= len(seqs[i]) <= n

Try it yourself

Solution

Title

Script

Lorem Ipsum is simply dummy text of the printing and typesetting industry. Lorem Ipsum has been the industry's standard dummy text ever since the 1500s, when an unknown printer took a galley of type and scrambled it to make a type specimen book.

Contrary to popular belief, Lorem Ipsum is not simply random text.

1  >>> a = [1, 2, 3]
2  >>> a[-1]
3  3

Get premium for instant access to all content and solutions

Upgrade