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 sizen
representing the original sequence.seqs
: a list of sequences of sizem
representing the sequences to be reconstructed.
Result
true
orfalse
, 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