# 444. Sequence Reconstruction

## 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) {
addNode(seq.get(0));
} else {
for(int i = 0; i < seq.size() - 1; i++) {
addNode(seq.get(i));
addNode(seq.get(i + 1));
// 加入子节点, 子节点增加一个入度
// [1,2] => 1 -> 2
// 1: [2]
int curr = seq.get(i);
int next = seq.get(i + 1);
if(map.get(curr).add(next)) {
indegree.put(next, indegree.get(next) + 1);
}
}
}
}
Queue<Integer> queue = new LinkedList<>();
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;
}
private void addNode(int node) {
if(!map.containsKey(node)) {
map.put(node, new HashSet<>());
indegree.put(node, 0);
}
}
}
```

按 <- 键看上一题！
443. String Compression

按 -> 键看下一题！
445. Add Two Numbers II