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.length1 <= n <= 104numsis a permutation of all the integers in the range[1, n].1 <= sequences.length <= 1041 <= sequences[i].length <= 1041 <= sum(sequences[i].length) <= 1051 <= sequences[i][j] <= n- All the arrays of
sequencesare unique. sequences[i]is a subsequence ofnums.
class Solution:
def sequenceReconstruction(self, org: List[int], seqs: List[List[int]]) -> bool:
n = len(org)
nums = set()
for seq in seqs:
for num in seq:
if num < 1 or num > n:
return False
nums.add(num)
if len(nums) < n:
return False
edges = defaultdict(list)
indegree = [0] * (n + 1)
for seq in seqs:
i = seq[0]
for j in seq[1:]:
edges[i].append(j)
indegree[j] += 1
i = j
q = deque()
for i in range(1, n + 1):
if indegree[i] == 0:
q.append(i)
cnt = 0
while q:
if len(q) > 1 or org[cnt] != q[0]:
return False
i = q.popleft()
cnt += 1
for j in edges[i]:
indegree[j] -= 1
if indegree[j] == 0:
q.append(j)
return cnt == nclass Solution {
public boolean sequenceReconstruction(int[] org, List<List<Integer>> seqs) {
int n = org.length;
Set<Integer> nums = new HashSet<>();
for (List<Integer> seq : seqs) {
for (int num : seq) {
if (num < 1 || num > n) {
return false;
}
nums.add(num);
}
}
if (nums.size() < n) {
return false;
}
List<Integer>[] edges = new List[n + 1];
for (int i = 0; i < edges.length; ++i) {
edges[i] = new ArrayList<>();
}
int[] indegree = new int[n + 1];
for (List<Integer> seq : seqs) {
int i = seq.get(0);
for (int j = 1; j < seq.size(); ++j) {
edges[i].add(seq.get(j));
++indegree[seq.get(j)];
i = seq.get(j);
}
}
Queue<Integer> q = new LinkedList<>();
for (int i = 1; i <= n; ++i) {
if (indegree[i] == 0) {
q.offer(i);
}
}
int cnt = 0;
while (!q.isEmpty()) {
if (q.size() > 1 || q.peek() != org[cnt]) {
return false;
}
++cnt;
int i = q.poll();
for (int j : edges[i]) {
--indegree[j];
if (indegree[j] == 0) {
q.offer(j);
}
}
}
return cnt == n;
}
}class Solution {
public:
bool sequenceReconstruction(vector<int>& org, vector<vector<int>>& seqs) {
int n = org.size();
unordered_set<int> nums;
for (auto& seq : seqs)
{
for (int num : seq)
{
if (num < 1 || num > n) return false;
nums.insert(num);
}
}
if (nums.size() < n) return false;
vector<vector<int>> edges(n + 1);
vector<int> indegree(n + 1);
for (auto& seq : seqs)
{
int i = seq[0];
for (int j = 1; j < seq.size(); ++j)
{
edges[i].push_back(seq[j]);
++indegree[seq[j]];
i = seq[j];
}
}
queue<int> q;
for (int i = 1; i <= n; ++i)
{
if (indegree[i] == 0) q.push(i);
}
int cnt = 0;
while (!q.empty())
{
if (q.size() > 1 || q.front() != org[cnt]) return false;
++cnt;
int i = q.front();
q.pop();
for (int j : edges[i])
{
--indegree[j];
if (indegree[j] == 0) q.push(j);
}
}
return cnt == n;
}
};func sequenceReconstruction(org []int, seqs [][]int) bool {
n := len(org)
nums := make(map[int]bool)
for _, seq := range seqs {
for _, num := range seq {
if num < 1 || num > n {
return false
}
nums[num] = true
}
}
if len(nums) < n {
return false
}
edges := make([][]int, n+1)
indegree := make([]int, n+1)
for _, seq := range seqs {
i := seq[0]
for _, j := range seq[1:] {
edges[i] = append(edges[i], j)
indegree[j]++
i = j
}
}
var q []int
for i := 1; i <= n; i++ {
if indegree[i] == 0 {
q = append(q, i)
}
}
cnt := 0
for len(q) > 0 {
if len(q) > 1 || org[cnt] != q[0] {
return false
}
i := q[0]
q = q[1:]
cnt++
for _, j := range edges[i] {
indegree[j]--
if indegree[j] == 0 {
q = append(q, j)
}
}
}
return cnt == n
}