### LeetCode  • ㊗️
• 大家
• offer
• 多多！

## Problem

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 of nums.

## Code

class Solution {
Map<Integer, Set<Integer>> map;
Map<Integer, Integer> indegree;

public boolean sequenceReconstruction(int[] nums, List<List<Integer>> sequences) {
map = new HashMap<>();
indegree = new HashMap<>();

for(List<Integer> seq: sequences) {
if(seq.size() == 1) {
} else {
for(int i = 0; i < seq.size() - 1; i++) {

// 加入子节点, 子节点增加一个入度
// [1,2] => 1 -> 2
// 1: 
int curr = seq.get(i);
int next = seq.get(i + 1);
indegree.put(next, indegree.get(next) + 1);
}
}
}
}

for(int key : indegree.keySet()) {
if(indegree.get(key) == 0){
queue.offer(key);
}
}

int index = 0;
while(!queue.isEmpty()) {
// 如果只有唯一解, 那么queue的大小永远都是1
if(queue.size() != 1) return false;

int curr = queue.poll();
if(curr != nums[index++]) return false;

for(int next: map.get(curr)) {
indegree.put(next, indegree.get(next) - 1);
if(indegree.get(next) == 0) {
queue.offer(next);
}
}
}

return index == nums.length;
}