# 444 Sequence Reconstruction

## 444.[ Sequence Reconstruction](https://leetcode.com/problems/sequence-reconstruction/description/)

## 1. Question

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 ≤ 104. 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
```

## 2. Implementation

**(1) BFS**

```java
class Solution {
    public boolean sequenceReconstruction(int[] org, List<List<Integer>> seqs) {
        Map<Integer, Set<Integer>> adjList = new HashMap<>();
        Map<Integer, Integer> inDegree = new HashMap<>();

        for (List<Integer> seq : seqs) {
            for (int num : seq) {
                adjList.putIfAbsent(num, new HashSet<>());
                inDegree.putIfAbsent(num, 0);
            }
        }

        for (List<Integer> seq : seqs) {
            // Cannot get any topological order for sequence whose length is less than 2
            if (seq.size() < 2) {
                continue;
            }

            for (int i = 0; i < seq.size() - 1; i++) {
                if (adjList.get(seq.get(i)).add(seq.get(i + 1))) {
                    inDegree.put(seq.get(i + 1), inDegree.get(seq.get(i + 1)) + 1);
                }
            }
        }

        // org can not be constructed from seqs because some number don't exist in org or sequences
        if (org.length != inDegree.size()) {
            return false;
        }

        Queue<Integer> queue = new LinkedList<>();

        for (int num : inDegree.keySet()) {
            if (inDegree.get(num) == 0) {
                queue.add(num);
            }
        }

        int count = 0;

        while (!queue.isEmpty()) {
            // Cannot uniquely construct sequence
            if (queue.size() > 1) {
                return false;
            }

            int curNum = queue.remove();
            ++count;

            for (int nextNum : adjList.get(curNum)) {
                inDegree.put(nextNum, inDegree.get(nextNum) - 1);
                if (inDegree.get(nextNum) == 0) {
                    queue.add(nextNum);
                }
            }
        }
        return count == org.length;
    }
}
```

## 3. Time & Space Complexity

BFS: 时间复杂度O(m)， m为seq中unique的数字个数，空间复杂度O(m)