444 Sequence Reconstruction

Search…
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)
269 Alien Dictionary
802 Find Eventual Safe States
Last modified 2yr ago
Copy link
Contents
444. Sequence Reconstruction
1. Question
2. Implementation
3. Time & Space Complexity
444. Sequence Reconstruction​

1. Question

2. Implementation

3. Time & Space Complexity

444. Sequence Reconstruction
