Formatted question description: https://leetcode.ca/all/444.html

# 444. Sequence Reconstruction

## Level

Medium

## Description

Check whether the original sequence org can be uniquely reconstructed from the sequences in `seqs`

. The `org`

sequence is a permutation of the integers from 1 to n, with 1 ≤ n ≤ 10^{4}. Reconstruction means building a shortest common supersequence of the sequences in `seqs`

(i.e., a shortest sequence so that all sequences in `seqs`

are subsequences of it). Determine whether there is only one sequence that can be reconstructed from `seqs`

and it is the `org`

sequence.

**Example 1:**

**Input:**

org: [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:**

org: [1,2,3], seqs: [[1,2]]

**Output:**

false

**Explanation:**

The reconstructed sequence can only be [1,2].

**Example 3:**

**Input:**

org: [1,2,3], seqs: [[1,2],[1,3],[2,3]]

**Output:**

true

**Explanation:**

The sequences [1,2], [1,3], and [2,3] can uniquely reconstruct the original sequence [1,2,3].

**Example 4:**

**Input:**

org: [4,1,5,2,6,3], seqs: [[5,2,6,3],[4,1,5,2]]

**Output:**

true

## Solution

If only one sequence can be reconstructed from `seqs`

, then `seqs`

must contain all adjacent subsequences of length 2 in `org`

. It is possible that `seqs`

contains a subsequence that has length greater than 2 and the elements in the subsequence are all adjacent in `org`

. Besides, `seqs`

must contain all the numbers in `org`

but can’t contain any number that is not in `org`

.

Use a map to store each number and its corresponding index in `org`

. Use an array of type `boolean`

to store whether each adjacent subsequence is contained in `seqs`

. Use a set to store the numbers in `seqs`

.

Loop over `org`

to fill in the map. For each sequence in `seqs`

, first check all the numbers in the sequence. If a number is greater than `org.length`

, then the number can’t be in `org`

, so return `false`

. Otherwise, add the number to the set. Then check each pair of adjacent numbers. If two adjacet numbers’ indices in `org`

are adjacent and the former number’s index is less than the latter number’s index, then set the element at the former number’s index in the `boolean`

array to `true`

. If the former number’s index is greater than or equal to the latter number’s index, then there is a conflict, so return `false`

.

After the loop, check the set’s size. If the set’s size is less than `org.length`

, then return `false`

. Then check all the elements in the `boolean`

array. If there is a `false`

, then return `false`

. Otherwise, return `true`

.

```
class Solution {
public boolean sequenceReconstruction(int[] org, List<List<Integer>> seqs) {
if (seqs == null)
return org == null;
if (seqs.size() == 0)
return org.length == 0;
Map<Integer, Integer> numIndexMap = new HashMap<Integer, Integer>();
int length = org.length;
for (int i = 0; i < length; i++)
numIndexMap.put(org[i], i);
boolean[] adjacentSequences = new boolean[length - 1];
Set<Integer> set = new HashSet<Integer>();
for (List<Integer> sequence : seqs) {
for (int num : sequence) {
if (num > length)
return false;
else
set.add(num);
}
int size = sequence.size();
for (int i = 1; i < size; i++) {
int num1 = sequence.get(i - 1), num2 = sequence.get(i);
int index1 = numIndexMap.getOrDefault(num1, -1);
int index2 = numIndexMap.getOrDefault(num2, -1);
if (index1 < 0 || index2 < 0 || index1 >= index2)
return false;
if (index2 - index1 == 1)
adjacentSequences[index1] = true;
}
}
if (set.size() < length)
return false;
for (boolean adjacentSequence : adjacentSequences) {
if (!adjacentSequence)
return false;
}
return true;
}
}
```