444. Sequence Reconstruction π
Description
You are given an integer array nums
of length n
where nums
is a permutation of the integers in the range [1, n]
. You are also given a 2D integer array sequences
where sequences[i]
is a subsequence of nums
.
Check if nums
is the shortest possible and the only supersequence. The shortest supersequence is a sequence with the shortest length and has all sequences[i]
as subsequences. There could be multiple valid supersequences for the given array sequences
.
- For example, for
sequences = [[1,2],[1,3]]
, there are two shortest supersequences,[1,2,3]
and[1,3,2]
. - While for
sequences = [[1,2],[1,3],[1,2,3]]
, the only shortest supersequence possible is[1,2,3]
.[1,2,3,4]
is a possible supersequence but not the shortest.
Return true
if nums
is the only shortest supersequence for sequences
, or false
otherwise.
A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements.
Example 1:
Input: nums = [1,2,3], sequences = [[1,2],[1,3]] Output: false Explanation: There are two possible supersequences: [1,2,3] and [1,3,2]. The sequence [1,2] is a subsequence of both: [1,2,3] and [1,3,2]. The sequence [1,3] is a subsequence of both: [1,2,3] and [1,3,2]. Since nums is not the only shortest supersequence, we return false.
Example 2:
Input: nums = [1,2,3], sequences = [[1,2]] Output: false Explanation: The shortest possible supersequence is [1,2]. The sequence [1,2] is a subsequence of it: [1,2]. Since nums is not the shortest supersequence, we return false.
Example 3:
Input: nums = [1,2,3], sequences = [[1,2],[1,3],[2,3]] Output: true Explanation: The shortest possible supersequence is [1,2,3]. The sequence [1,2] is a subsequence of it: [1,2,3]. The sequence [1,3] is a subsequence of it: [1,2,3]. The sequence [2,3] is a subsequence of it: [1,2,3]. Since nums is the only shortest supersequence, we return true.
Constraints:
n == nums.length
1 <= n <= 104
nums
is a permutation of all the integers in the range[1, n]
.1 <= sequences.length <= 104
1 <= sequences[i].length <= 104
1 <= sum(sequences[i].length) <= 105
1 <= sequences[i][j] <= n
- All the arrays of
sequences
are unique. sequences[i]
is a subsequence ofnums
.
Solutions
Solution 1: Topological Sorting
We can first traverse each subsequence seq
. For each pair of adjacent elements $a$ and $b$, we establish a directed edge $a \to b$. At the same time, we count the in-degree of each node, and finally add all nodes with an in-degree of $0$ to the queue.
When the number of nodes in the queue is equal to $1$, we take out the head node $i$, remove $i$ from the graph, and decrease the in-degree of all adjacent nodes of $i$ by $1$. If the in-degree of the adjacent nodes becomes $0$ after decreasing, add these nodes to the queue. Repeat the above operation until the length of the queue is not $1$. At this point, check whether the queue is empty. If it is not empty, it means there are multiple shortest supersequences, return false
; if it is empty, it means there is only one shortest supersequence, return true
.
The time complexity is $O(n + m)$, and the space complexity is $O(n + m)$. Where $n$ and $m$ are the number of nodes and edges, respectively.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
|