444 Sequence Reconstruction

1. Question

Check whether the original sequenceorgcan be uniquely reconstructed from the sequences inseqs. Theorgsequence is a permutation of the integers from 1 to n, with 1 ≤ n ≤ 104. Reconstruction means building a shortest common supersequence of the sequences inseqs(i.e., a shortest sequence so that all sequences inseqsare subsequences of it). Determine whether there is only one sequence that can be reconstructed fromseqsand it is theorgsequence.
Example 1:
1
Input:
2
3
org: [1,2,3], seqs: [[1,2],[1,3]]
4
5
6
Output:
7
8
false
9
10
11
Explanation:
12
13
[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.
Copied!
Example 2:
1
Input:
2
org: [1,2,3], seqs: [[1,2]]
3
4
5
Output:
6
false
7
8
9
Explanation:
10
11
The reconstructed sequence can only be [1,2].
Copied!
Example 3:
1
Input:
2
org: [1,2,3], seqs: [[1,2],[1,3],[2,3]]
3
4
5
Output:
6
true
7
8
9
Explanation:
10
The sequences [1,2], [1,3], and [2,3] can uniquely reconstruct the original sequence [1,2,3].
Copied!
Example 4:
1
Input: org: [4,1,5,2,6,3], seqs: [[5,2,6,3],[4,1,5,2]]
2
3
4
Output: true
Copied!

2. Implementation

(1) BFS
1
class Solution {
2
public boolean sequenceReconstruction(int[] org, List<List<Integer>> seqs) {
3
Map<Integer, Set<Integer>> adjList = new HashMap<>();
4
Map<Integer, Integer> inDegree = new HashMap<>();
5
6
for (List<Integer> seq : seqs) {
7
for (int num : seq) {
8
adjList.putIfAbsent(num, new HashSet<>());
9
inDegree.putIfAbsent(num, 0);
10
}
11
}
12
13
for (List<Integer> seq : seqs) {
14
for (int i = 0; i < seq.size() - 1; i++) {
15
if (adjList.get(seq.get(i)).add(seq.get(i + 1))) {
16
inDegree.put(seq.get(i + 1), inDegree.get(seq.get(i + 1)) + 1);
17
}
18
}
19
}
20
21
// org can not be constructed from seqs because some number don't exist in org or sequences
22
if (org.length != inDegree.size()) {
23
return false;
24
}
25
26
Queue<Integer> queue = new LinkedList<>();
27
28
for (int num : inDegree.keySet()) {
29
if (inDegree.get(num) == 0) {
30
queue.add(num);
31
}
32
}
33
34
int count = 0;
35
36
while (!queue.isEmpty()) {
37
// Cannot uniquely construct sequence
38
if (queue.size() > 1) {
39
return false;
40
}
41
42
int curNum = queue.remove();
43
++count;
44
45
for (int nextNum : adjList.get(curNum)) {
46
inDegree.put(nextNum, inDegree.get(nextNum) - 1);
47
if (inDegree.get(nextNum) == 0) {
48
queue.add(nextNum);
49
}
50
}
51
}
52
return count == org.length;
53
}
54
}
Copied!

3. Time & Space Complexity

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